技能树

【题目描述】

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

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

【输入格式】

第一行两个数N和M,如题所述

之后N行,第i行,有n+1-i个数.表示一个技能树.

【输出格式】

输出一个数,表示最大威力值之和

【输入样例】

4 5
1 1 1 1
1 2 1
1 1
1

【输出样例】

6

【数据范围与约定】

对于40%的数据,N<=10；

对于100%的数据,N<=50,M<=500,所有数据都在longint之内。