Surviving the Springheads

Shirost is addicted to a game called "Deadly Company". In the game, as a contract worker for a company, he must collect scrap on a derelict industrial planet. During his expedition he encounters a monster called a springhead. A springhead moves very quickly when it is not observed, but if Shirost fixes his gaze on its corridor, the springhead stops moving. However, if a springhead ever reaches Shirost’s position, it will kill him immediately.

Currently, Shirost stands at the intersection of \(n\) infinitely long corridors. He is aware that there will be \(m\) springheads. The \(i\)th springhead appears at time \(t_i\) on corridor \(x_i\), exactly \(y_i\) meters away from him.

Time proceeds in discrete moments. At each moment \(j\), the following three events occur in order:

1. At the beginning of moment \(j\), any springhead with \(t_i = j\) appears in its corresponding corridor \(x_i\) at distance \(y_i\) from Shirost.
2. Shirost chooses one corridor to fix his gaze on.
3. Every springhead that has already appeared and is not in the corridor being gazed at moves \(k\) meters closer to him. If any springhead reaches his position (i.e. its distance becomes \(\le 0\)), then Shirost dies exactly at moment \(j\).

Shirost, being clever, can choose which corridor to gaze at each moment in order to delay his eventual death for as long as possible. If his last moment of survival is \(j-1\) (that is, he dies at moment \(j\)), then the answer to the problem is \(j-1\). If he can avoid death indefinitely, output -1.

Note on distances: All formulas should be written in LaTeX format. For example, distances and times appear as \(y_i\), \(t_i\), and the monster movement as \(k\) meters.

inputFormat

The first line of input contains three integers \(n\), \(m\), and \(k\) — the number of corridors, the number of springheads, and the distance (in meters) that any moving springhead covers in one moment.

Each of the next \(m\) lines contains three integers \(t_i\), \(x_i\), and \(y_i\), representing that a springhead appears at time \(t_i\) on corridor \(x_i\) at a distance of \(y_i\) meters from Shirost.

If \(m = 0\), then no additional lines follow.

outputFormat

Output a single integer. If Shirost dies at moment \(j\), print \(j-1\); if he can survive indefinitely, print -1.

sample

3 0 5

-1