1903: 技能树
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 13 Solved: 10
[Submit] [Status] [Web Board] [Creator:]
Description
热爱电子娱乐的同学们对于技能树一定不陌生.就是说,要先学习低级的垃圾技能,特定的几个垃圾技能学会了,才能学习更强的技能.比如说,要先学火球术和烈火墙,才能学习地狱烈焰.科技树也是一样.要先研究出电力和内燃机,才能研究工业学.那么,现在我们把问题简化。
这是一个技能树(或者科技树).格子上的数,是威力值.要先学会第一排第二个和第三个,才能学会第二排的第二个.每个技能学习的前提都是左上和右上的两个技能.假设现在有一个第一层有N个技能的技能树,而且技能点是有限的,只能学习M个技能,我们想知道最大的威力值之和是多少。
这是一个技能树(或者科技树).格子上的数,是威力值.要先学会第一排第二个和第三个,才能学会第二排的第二个.每个技能学习的前提都是左上和右上的两个技能.假设现在有一个第一层有N个技能的技能树,而且技能点是有限的,只能学习M个技能,我们想知道最大的威力值之和是多少。
Input
第一行两个数N和M,如题所述
之后N行,第i行,有n+1-i个数.表示一个技能树。
之后N行,第i行,有n+1-i个数.表示一个技能树。
Output
输出一个数,表示最大威力值之和。
Sample Input Copy
4 5
1 1 1 1
1 2 1
1 1
1
Sample Output Copy
6
HINT
【数据规模】
对于40%的数据,N<=10
对于100%的数据,N<=50,M<=500,所有数据都在int之内.
对于40%的数据,N<=10
对于100%的数据,N<=50,M<=500,所有数据都在int之内.