少林阵法乱
Description
小李飞刀特别喜欢武功，他听说少林寺武功闻名天下，不由心生向往，有一天他不畏路途遥远，跋山涉水来到了少林寺，只为在少林寺中学到一两个绝学。哪知，他到了少林寺才知道要学到正宗的少林绝学，需要剃发为僧，听到这个消息后，小李飞刀像打了霜的茄子一样。无奈之中，小李飞刀只好收拾好行李准备打道回府。然而，在这时，少林方丈看他骨骼精奇，是百年难得一见的练武奇才。决定给他一个机会。方丈对他说：“少林寺已经布下阵法，只要你能闯过阵法，就破例教你少林绝学。”
阵法总共有n层，第i层有i个洞穴，第i层的第j个洞穴只能通往第i+1层的第j个和第j+1个洞穴，每个洞穴中有一个武僧把守，每层小李飞刀需要将其中一个洞穴的武僧打败才能进入下一层。如果他能通过第n层，那么他就能学到少林绝学。小李飞刀和武僧打斗时会受一定的伤，现在知道他与每个武僧打斗时受到的伤害值，请你编写一个程序让他能以最少代价破阵。
Format
Input
第一行输入一个整数n（0<n<=100）,表示阵法有n层。
然后输入n行数字，其中第i(1 <= i <= n)行有i个整数（所有整数在区间[0,100]），分别表示小李飞刀与该武僧打斗会受的伤害。
Output
输出小李飞刀最少需要受到的伤害值。
Samples
4
5
7 4
4 3 2
6 7 1 3
12