OJ现已增加邮箱找回密码功能，还没有绑定邮箱的同学们请抓紧时间，以免密码丢失无法找回


问题1473--收烟花

1473: 收烟花

时间限制: 1 Sec  内存限制: 128 MB
提交: 132  解决: 47
[提交] [状态] [讨论版] [命题人:]

题目描述

临近过年，放烟花的人也变多了，你作为一个执勤人员接到任务要阻止人们放烟花，你在一个由k*k个小格子组成的正方形中执勤。你的初始位置在（1,1），执勤区域右下角的坐标为（k,k）。在边长为k的正方形内你只能向右走或者向下走，这个区域中有n个放烟花的人，每个人手中都有若干的烟花，现在想知道最后最多可以收取多少烟花。

输入

第一行输出一个整数n，k表示放烟花人数的数量和区域的边长
下面n行表示放烟花的人的坐标（左上角表示（1,1），右下角表示为（k,k））
每行输入三个整数  x , y, v 表示放烟花的人的坐标和手中的烟花数
数据范围
1<=n<=100000
1<=k<=1000
1<=x,y,v<=1000
有可能存在多个放烟花的人在同一个位置，这时候执勤人员可以把他们的烟花全部收走

输出

输出一个整数表示最多可以收取多少的烟花数量


样例输入 Copy 

2 5
3 3 12
4 5 10

样例输出 Copy 

22

来源/分类

 
[提交] [状态]