技能树

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 skill.in 输出文件 skill.out

Description

       热爱电子娱乐的同学们对于技能树一定不陌生.就是说,要先学习低级的垃圾技能,特定的几个垃圾技能学会了,才能学习更强的技能.比如说,要先学火球术和烈火墙,才能学习地狱烈焰.科技树也是一样.要先研究出电力和内燃机,才能研究工业学.那么,现在我们把问题简化,

这是一个技能树(或者科技树).格子上的数,是威力值.要先学会第一排第二个和第三个,才能学会第二排的第二个.每个技能学习的前提都是左上和右上的两个技能.假设现在有一个第一层有N个技能的技能树,而且技能点是有限的,只能学习M个技能,我们想知道最大的威力值之和是多少.

Input Format
       第一行两个数N和M,如题所述
       之后N行,第i行,有n+1-i个数.表示一个技能树.
Output Format
       输出一个数,表示最大威力值之和
Sample Input
4 5
1 1 1 1
1 2 1
1 1
1
Sample Output
6
Data Limit
       对于40%的数据,N<=10
       对于100%的数据,N<=50,M<=500,所有数据都在longint之内.