TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3785
  • 题目
  • P3785打架之技能
    限制 : 时间限制 : - MS   空间限制 : 165536 KB
    评测说明 : 1000ms
    问题描述

    路漫漫之修远兮,吾将上下而打架。打架的路上,要先学习低级的垃圾技能,特定的几个垃圾技能学会了,才能学习更强的技能.比如说,要先学降龙十八掌和旋风扫叶腿,才能学九阴真经.

    如图是一个技能墙.格子上的数,是打架值.要先学会上一排连续的两个,才能学会这一排的对应格子(当然第一排的可以随意选).例如选了图中的①和②,才能选③。每个技能学习的前提都是左上和右上的两个技能. 假设现在有第一层有N个技能的技能墙,且技能点是有限的,只能学习M个技能,我们想知道最大的打架值之和是多少.

    输入格式

    第一行,两个个整数N,M。

    接下来N行,每行依次为N,N-1,…,1个整数,表示技能墙的每一排。

    输出格式

    一行,一个整数,表示最大得分。

    样例输入

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

    样例输出

    6

    提示

    40%的数据保证,  N<=10

    100%的数据保证,  N<=500,M<=500, 所有数据(包括答案)都在int之内.


    来源  ZMY