题目描述

某天，小白准备去跳伞。

下落过程中的区域有着危险值，危险值越小代表越安全。 小白希望能够平安落地，同时他不希望垂直下落到下一高度（同一行代表同一高度，第一行高度最高），因此他必须选择滑落到下一高度的其他位置，并且滑落到下一高度的过程中，小白能够滑落到下一高度的任意位置。

请问小白同学通过危险区域的最低危险值之和是多少？

输入格式

第一行一个整数 h，代表危险区域大小 h×h，

接下来 h 行，每行有 h 个危险值 dangeri

输出格式

输出一个整数，表示小白通过这片危险区域最小危险值之和

3

1 2 3

4 5 6

7 8 9

小白可以选择的下落区域有:

1-5-9、1-5-7、1-6-7、1-6-8、2-4-8、2-4-9、2-6-7、2-6-8、3-4-8、3-4-9、3-5-7、3-5-9

计算可得 1-5-7 所得危险总和13为最小危险值。

100% 数据满足，0＜h≤2000，-2×106≤dangeri≤2×106 
题目数据量较大，请使用scanf输入