#1044. mm和tt吃糖果

内存限制:512 MiB 时间限制:750 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Akatsuki

题目描述

mm和tt来到渡渡鸟王国旅行,渡渡鸟王国是一片 块格子的花园,每块格子有一个坐标,左上角为入口 ,右下角为出口

花园的k个格子上有一定数量的糖果,作为两枚吃货,mm和tt致力于收集尽可能多的糖果。

两人初始是在入口为 ,由于旅行时间紧张,两人只能向目的地方向行走(即向右走或向下走);另外,为了防止花园地面塌陷,tt决定等mm先行到达出口再从入口出发。

mm和tt每到达一个有糖果的格子,便会拿走格子上的糖果,当然,对于同一个格子,mm拿走了格子上的糖果,tt再到达时便没有糖果可拿了。作为好朋友,mm和tt会将拿到的糖果一起分享,她们想知道如何走才能使拿到的糖果数之和最大。

输入格式

第一行两个整数

接下来 行,每行三个正整数 ,表示在 处有 颗糖果。

保证对于任意的 不存在

输出格式

输出一行一个整数,表示mm和tt能获得的最大糖果总数。

样例

样例输入

8 8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14

样例输出

67

数据范围与提示