A spillway is built as a triangular array of terraces. Row 0 has one terrace; row i has i + 1 terraces. Water starts on the single terrace of row 0. From the terrace at position j of row i it flows to the terrace at position j or position j + 1 of row i + 1 (the two terraces directly beneath it). Each terrace holds an integer weight that is added to the running total as the water passes over it, including the apex and the final terrace reached in the bottom row.

Determine the minimum possible total over all descents from the apex to any terrace in the bottom row.

Input format

Line 1: an integer T, the number of rows. Next T lines: line i (0-indexed) contains i + 1 integers, the terrace weights of that row.

Output format

A single integer: the minimum total weight of a descent from the apex to the bottom row.

Constraints

• 1 <= T <= 200
• 0 <= each terrace weight <= 1000

4
2
3 4
6 5 7
4 1 8 3

11

1
5

5