Cho một ma trận có kích thước ~n \times n~. Hàng thứ ~i~, cột thứ ~j~ là ô ~(i, j)~, mỗi ô sẽ có một trọng số ~A_{i,j}~, trọng số của một đường đi tổng các ~A_{i,j}~ nằm trên đường đi đó. Trong một lần di chuyển, giả sử đang đứng ở ô ~(i, j)~ bạn chỉ có thể đi tới các ô ~(i+1, j-1)~, ~(i+1, j)~, ~(i+1, j+1)~ (các ô cần đảm bảo nằm bên trong ma trận).

Tìm đường đi có trọng số nhỏ nhất xuất phát từ một ô bất kỳ ở hàng 1 đến 1 ô bất kỳ ở hàng ~n~.

Input

• Dòng đầu tiên gồm số nguyên dương ~n~ (~1 \leq n \leq 100~).
• ~n~ dòng tiếp theo, mỗi dòng gồm ~n~ số nguyên dương số thứ ~j~ là ~A_{i,j}~ (~-200 \leq A_{i,j} \leq 200~).

Output

• In ra trọng số nhỏ nhất tìm được.

Example Test

Input 1

3
2 1 3
6 5 4
7 8 9

Output 1

13