Nam cần tìm đường đi từ đỉnh núi xuống chân núi. Để thực hiện việc này, Nam cần qua nhiều chặng đường, mỗi chặng đường tương ứng với một khoảng thời gian nhất định.

Để thuận tiện cho việc tính toán, Nam mô tả việc đi từ đỉnh núi đến chân núi tương ứng đi từ đỉnh tam giác đến đáy tam giác và sử dụng các số tự nhiên để mô tả thời gian của các chặng đường. Mỗi chặng đường, chỉ được đi từ số ở hàng trên xuống một trong hai số đứng kề bên phải hay bên trái ở hàng dưới, và cộng các số trên đường đi chính là tổng thời gian.

Ví dụ:

                                                                    7
                                                                3       8
                                                            9       1       2
                                                        5       6       4       11
                                                    22      44      66      54      15

Đường đi ~7, 3, 1, 6, 44~ có tổng thời gian là ~7+3+1+6+44 = 61~,

Đường đi ~7, 3, 9, 5, 22~ có tổng thời gian là ~7+3+9+5+22 = 46~,

Đường đi ~7, 8, 2, 11, 15~ có tổng thời gian là ~7+8+2+11+15 = 43~,

Yêu cầu: Tìm tổng thời gian ít nhất để Nam có thể đi từ đỉnh núi đến chân núi.

Dữ liệu vào:

• Dòng 1: Chứa một số nguyên dương ~N (1 \le N \le 1000)~ là số chặng đường từ đỉnh núi đến chân núi

• ~N~ dòng tiếp theo: Dòng thứ ~i~ chứa ~i~ số nguyên thể hiện chiều dài của các chặng đường, mỗi số cách nhau ít nhất một dấu cách. Chiều dài mỗi chặng đường không quá ~1000~.

Dữ liệu ra:

• Một số nguyên duy nhất là tổng thời gian ít nhất để Nam có thể đi từ đỉnh núi đến chân núi.

Sample Input 1

1
2

Sample Output 1

2

Sample Input 2

  3
  2
 3 4
5 2 7

Sample Output 2

7

Sample Input 3

      5
      7
     3 8
    9 1 2
   5 6 4 11
22 44 66 54 15

Sample Output 3

2