Problem Description

There are $m$ zombies that are going to attack the city.

The zombies set off one by one from a zombie nest that is $(n+1)$ meters away from the city. Each zombie moves at a speed of $1$ meter per second, towards the city. The time interval between consecutive zombies leaving the nest is $1$ second. Let the time when the first zombie departs be the beginning of the $1$-st second.

This means:

• At the end of the $1$-st second, there is a zombie $1$ meter away from the nest.
• At the end of the $2$-nd second, there are zombies $1,2$ meters away from the nest.
• At the end of the $3$-rd second, there are zombies $1,2,3$ meters away from the nest.
• And so on.

When a zombie is $(n+1)$ meters away from the nest, it arrives at the city.

Now we place $k$ bombs on the road to defend the city. For each bomb, we know the following information:

• The bomb's position (i.e., its distance from the nest).
• The bomb's explosion radius.
• The time when the bomb is installed.

For a bomb with radius $r$, suppose it is installed at position $x$ at time $t$. This bomb will kill a zombie located at position $y$ if and only if $|x-y|\le r$ holds at time $t$. Zombies that have already arrived in the city will not be killed. A killed zombie cannot continue moving.

Bombs may be installed at any time and position; in particular, there may be multiple bombs at the same time (and/or) at the same position.

Find the number of zombies that arrive in the city.

Input Format

The first line contains three positive integers $n,m,k$ ($1\le n,m,k\le 200$).

The next $k$ lines each contain three integers $x,r,t$ ($1\le x\le n$，$0\le r\le n$，$1\le t\le 500$), describing a bomb, where:

• The bomb is installed $x$ meters away from the nest.
• The explosion radius is $r$ meters.
• The installation time is at the end of the $t$-th second.

Output Format

Output one line with one integer: the number of zombies that arrive in the city.

6 3 3
3 1 2
5 0 7
4 4 8

1

7 7 1
3 2 6

2

3 3 1
3 3 3

0

Hint

Sample Explanation

The explanation for sample 1 is shown in the table below.

Subtasks

Translated by ChatGPT 5