芳芳的数字三角形
Time Limit: 1000 ms
Memory Limit: 65536 KiB
Problem Description
芳芳学了动态规划之后,觉得数字三角形问题太简单了。然后,爱思考的芳芳想了一个看上去复杂一点的问题,假如对最后的结果对100取余,该怎么计算呢?聪明的芳芳,想都没想就秒杀了,芳芳想考考你,你可以解决吗?
Input
多组输入。不超过10组数据,输入数据的第1行是数字三角形的行数n,1≤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