Microspikes

In a study of domestic power use, researchers built a simulator for residential homes. For each home the software simulates the power consumption of its appliances. The goal is to identify microspikes in power usage: short intervals during which the total power consumption rises above a specified limit.

Before a simulation starts, all appliances are off (drawing no power). At various times during the simulation an appliance increases or decreases its power draw. Every time this happens the simulator emits a record containing the appliance number, the time in seconds since that appliance's previous change (or since the start of the simulation for its first change), and the change in power level in watts.

For any single appliance the records appear in chronological order. However, records for different appliances are interleaved arbitrarily, so a record for appliance $A$ written before a record for appliance $B$ does not imply that $A$'s event occurred before $B$'s.

Given a power threshold $M$ and a time threshold $S$, a microspike is a maximal interval during which the total power $P$ stays strictly above $M$ ($P > M$) and whose duration $D$ in seconds satisfies $1 \le D \le S$. A microspike is counted only when both its start (total power rising strictly above $M$) and its end (total power falling back to $M$ or below) are reported. Appliances that are still above the threshold when the simulation ends are never turned off, so an interval that never returns to $M$ or below is not counted.

Read the records for one or more simulations and count how many microspikes occur in each.

The input describes one or more simulations. Each simulation begins with a line holding three integers $T$, $M$, and $S$ separated by single spaces, where $T$ is the total simulation time in seconds ($0 \le T \le 100000$), $M$ is the power threshold ($0 \le M \le 10^9$), and $S$ is the time threshold ($1 \le S \le 1000$).

The header line is followed by up to $N$ power-change lines ($0 \le N \le 1000000$). Each holds three integers $a$, $t$, and $p$ separated by single spaces: $a$ is the appliance number ($1 \le a \le 100000$); $t$ is the time in seconds since that appliance's previous change ($0 \le t \le T$); and $p$ is the change in power level in watts ($-10000 \le p \le 10000$). A line 0 0 0 marks the end of the power-change lines for the current simulation.

A simulation header line equal to 0 0 0 ends the entire input. You may assume that the power level of any single appliance never becomes negative and that the total power consumption never exceeds $1000000000$. All power changes take effect instantaneously at the start of the indicated second.

For each simulation, print a single line containing the number of microspikes observed.

Total power consumption for the example input. The labels on the horizontal axis mark the start of each second. All power changes take effect instantaneously at the start of a second. The bar drawn at time $10$ is not part of the simulation; it is shown only to indicate the power level that continues after the simulation ends.