레이팅 미적용Vito is obsessed with the new hit video game Zombie Apocalypse. He is currently
facing the following challenge: \(m\) zombies are headed toward the city and will
attack it if he doesn’t stop them.
More specifically, the zombies are located in a secret cave \(n\) meters away from the
city and leave the cave one by one. The zombies walk toward the city at a speed
of 1 meter per second, and there is a one-second pause between two consecutive
zombies leaving the cave.
Thus, after the first second there is one zombie 1 meter away from the cave; after the second second there
are zombies 1 and 2 meters away; after the third second there are zombies 1, 2, and 3 meters away, and so
on. Whenever a zombie passes the \(n\)-th meter, it reaches the city.
According to the rules of the game, Vito is allowed to drop \(k\) bombs on the path between the cave and
the city in order to stop the attack. For each bomb, he has chosen:
• the position (distance from the cave) where the bomb is dropped,
• the radius of the bomb, and
• the time (in seconds) when the bomb is dropped.
A bomb with radius \(r\) dropped at position \(x\) at time \(t\) will destroy a zombie if it is located at position \(y\)
at time \(t\) such that the distance between \(x\) and \(y\) is at most \(r\) meters, i.e., |\(x - y\)| ≤\(r\). Zombies that have
already reached the city are not affected by bombs. Once a zombie is destroyed, it can no longer continue
its journey toward the city.
Vito can choose for the bombs to be dropped with any position, radius, and time, and multiple bombs
can occur at the same time, even at the same position.
Given Vito’s choices for the \(k\) bombs, determine how many zombies will reach the city.
Subtask 1 (13 points): \(m = 1\)
Subtask 2 (27 points): \(k = 1\)
Subtask 4 (30 points): No additional constraints.
In the first line there are three natural numbers \(n\), \(m\), and \(k\) (\(1 \le n\), m, \(k \le 200\)), the length of the path
between the cave and the city, the number of zombies, and the number of bombs.
In each of the following \(k\) lines there are three natural numbers \(x\), \(r\), and \(t\) (\(1 \le x \le n\), \(0 \le r \le n\), 1 ≤
\(t \le 500\)), the distance in meters from the cave at which one of the bombs is dropped, the radius of that
bomb in meters, and the time at which the bomb is dropped in seconds.
In the first and only one line, write one number, the number of zombies that managed to reach the city.
6 3 3
3 1 2
5 0 7
4 4 817 7 1
3 2 623 3 1
3 3 30Clarification of the first example:
time: 0,
cave: {z, z, z},
path: (0, 0, 0, 0, 0, 0),
city: {}
time: 1,
cave: {z, z},
path: (z, 0, 0, 0, 0, 0),
city: {}
time: 2,
cave: {z},
path: (z, z, 0, 0, 0, 0),
city: {}
time: 2,
cave: {z},
path: (z, z, 0, 0, 0, 0),
city: {}
time: 2,
cave: {z},
path: (z, 0, 0, 0, 0, 0),
city: {}
time: 3,
cave: {},
path: (z, z, 0, 0, 0, 0),
city: {}
time: 4,
cave: {},
path: (0, z, z, 0, 0, 0),
city: {}
time: 5,
cave: {},
path: (0, 0, z, z, 0, 0),
city: {}
time: 6,
cave: {},
path: (0, 0, 0, z, z, 0),
city: {}
time: 7,
cave: {},
path: (0, 0, 0, 0, z, z),
city: {}
time: 7,
cave: {},
path: (0, 0, 0, 0, z, z),
city: {}
time: 7,
cave: {},
path: (0, 0, 0, 0, 0, z),
city: {}
time: 8,
cave: {},
path: (0, 0, 0, 0, 0, 0),
city: {z}
time: 8,
cave: {},
path: (0, 0, 0, 0, 0, 0),
city: {z}
time: 8,
cave: {},
path: (0, 0, 0, 0, 0, 0),
city: {z}