芳芳的数字三角形

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

 

芳芳学了动态规划之后,觉得数字三角形问题太简单了。然后,爱思考的芳芳想了一个看上去复杂一点的问题,假如对最后的结果对100取余,该怎么计算呢?聪明的芳芳,想都没想就秒杀了,芳芳想考考你,你可以解决吗?

Input

 

多组输入。不超过10组数据,输入数据的第1行是数字三角形的行数n1≤n≤24。接下来n行是数字三角形各行中的数字。所有数字在0..10000之间。

Output

 

每组数据输出一个数字,对100取余后,最大的结果。

Sample Input

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
2
1
99 1

Sample Output

30
2

Hint

 

Source

cuizhe