2644. Jack

单点时限: 5.0 sec

内存限制: 256 MB

A team of airborne troops are ready to complete some missions.

The battlefield was divided into a grid of n*n, this team can be air-dropped at any place on time 0. In every time unit after landing, they can go to the grid left, right, up or down to the current grid, or they can just stay.

On their mission list, each mission is described as three integers: t, r and c, represents a task that must be completed exactly at time t on the grid (r, c).

Obviously, with limits of time, not all missions can be done.

The captain, Jack, struggling making decisions, wants to know how many missions they can complete at most.

输入格式

The input contains serveral cases:

For each case:

  • The first line contains two integers n and m, 1<=n<=1000, 1<=m<=10000, n represents the size of the battlefield and m represents the number of missions on the list.

  • Following m lines, each one describes a mission using three integers, t, r and c.

The input is terminated by n=m=0.

输出格式

One integer in one line represents the maximum number of mission that can be completed.

样例

Input
2 2
1 1 1
2 2 2
0 0
Output
1

1 人解决,3 人已尝试。

2 份提交通过,共有 11 份提交。

9.9 EMB 奖励。

创建: 11 年前.

修改: 2 年,11 月前.

最后提交: 11 年前.

来源: 多校联合比赛BNU站

题目标签