Felix is on the top of a pyramid! He is trying to climb down to the lowest level, where Zihe is at.

At the top floor of the pyramid, there is ~1~ way to get down, with a cost of ~c_1~. At the second highest floor of the pyramid, there are ~2~ ways to get down, each with a cost of ~c_2~ and ~c_3~, and so on. Unfortunately, he can only land on adjacent rooms in the floor below him. Can you minimize the cost Felix will take to get to the lowest floor?

For example, in the pyramid:

   2
  3 4
 6 5 7
4 1 8 3

Felix will start at 2, then go to 3, then 5, and finally land on the lowest floor in the room with cost 1. This accumulates a total cost of 11.

Input Specification

The first line of input will contain an integer ~N~.

The next ~N~ lines of input will contain ~i~ integers, for ~1 \le i \le N~.

Output Specification

Output a single integer followed by newline, the minimum path Felix will take to reach the bottom floor where Zihe is at.

Constraints

Subtask 1 [30%]

~1 \le N \le 100~

~1 \le c_i \le 100~

Subtask 2 [70%]

~1 \le N \le 1000~

~1 \le c_i \le 10^9~

Sample Input 1

4
2
3 4
6 5 7
4 1 8 3

Sample Output 1

11