위에서 아래로 내려오는 숫자 삼각형이 주어진다. 맨 위 층에서 출발하여 제일 아래 층으로 내려오면서 거쳐간 숫자들의 합을 구하려고 한다.

아래 층으로 이동할 때는 현재 위치에서 대각선 왼쪽 아래 또는 대각선 오른쪽 아래로만 한 칸씩 이동할 수 있다.

삼각형의 높이 \(R\)과 각 위치의 숫자들이 주어졌을 때, 맨 아래 층에 도착했을 때 얻을 수 있는 숫자 합의 최댓값을 구하는 프로그램을 작성하시오.

예를 들어, 아래와 같은 높이 \(5\)의 삼각형이 있을 때:

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

\(7 \to 3 \to 8 \to 7 \to 5\) 경로를 따라 이동하면 합이 \(30\)이 되며, 이 값이 얻을 수 있는 최댓값이다.

입력

첫째 줄에 삼각형의 높이 \(R\)이 주어진다. (\(1 \le R \le 1,000\))

둘째 줄부터 \(R\)개의 줄에 걸쳐 각 층의 숫자 정보가 입력된다.

\(i\)번째 줄에는 \(i\)개의 정수가 공백으로 구분되어 주어진다. 각 값들의 범위는 \(0 \sim 100\)이다.

출력

맨 아래 층까지 내려왔을 때 얻을 수 있는 숫자 합의 최댓값을 출력한다.

예제 입력 1

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

예제 출력 1

30

출처

ioi 1994