#1207. Day4E. ZJY 的幼儿园清扫惨案

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

题目描述

魔王 ZJY 横征暴敛,作恶无数,他喜欢吃糖果,并发誓要把富有糖果的渡渡鸟幼儿园清扫干净。但见 SL 与 WYB 仍谈笑风生,SL 和 WYB 想逃脱 ZJY 可笑的声讨,并用实力继续嘲讽 ZJY。

Cvi1e.jpg

渡渡鸟幼儿园是一栋拥有 个方格房间的方阵形迷宫,每间相邻房间之间有门可以互相通行。SL 和 WYB 最初在方阵的西北角(上北下南),位置 ,但幼儿园与外界唯一的出入口,是东南角房间 的超空间航路。每经过一扇门,SL 和 WYB 都要花费固定的时间。他们想要尽快到达出口。

另外呢,为了逗小朋友开心,幼儿园的有些房间里放着一些糖果。SL 和 WYB 经过的时候可以顺带把这个房间里的糖果全部捎走,不需要多余的时间。

他们俩想要在最短的时间内带走尽可能多的糖果,这样子 ZJY 能找到的糖果就变少了。

注:渡渡鸟幼儿园的坐标系统里,房间由坐标 表示, 表示到从北方边界起始的标号, 表示从西方边界起始的标号。

输入格式

第一行两个整数

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

保证对于任意的 不存在

输出格式

输出一行一个整数,表示 SL 和 WYB 能带走的最大糖果总数。

样例

样例输入

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

数据范围与提示