Description
Dogeon is trying to build a marble machine that can play music. The machine is composed of a series of tracks, each of which has a different length. The machine is designed to play music by releasing marbles from the top of the machine. The marbles will then roll down the tracks and hit various instruments, creating a melody.
Currently, he is designing a new track for the machine. He wants to know how it performs in different scenarios.
The track is composed of four conveyor belts with same length and same speed. Four of them are facing a gate in the middle of the track. In each second:
- Marbles can move one unit towards the gate
- Marble on the gate will be released and leave the track
- Two marbles can't be on the same unit
With given configuration of the track, Dogeon wants to know how many marbles will be released in the first \(T\) seconds.
Wintergatan - Marble Machine (music instrument using 2000 marbles)
Input
The first line of input contains three integers \(N\), \(T\), and \(L\), the number of marbles, the number of seconds, and the length of the track, respectively.
For the next \(N\) lines, \(i\)-th line contains two integers \(x_i\) and \(y_i\). Denote that marble \(i\) is \(x_i\) units away from the gate on the \(y_i\)-th conveyor belt.
\(N \quad T \quad L\)
\(x_1 \quad y_1\)
\(x_2 \quad y_2\)
\(\vdots\)
\(x_N \quad y_N\)
Constraints
- \(1 \leq N \leq 10^5\)
- \(1 \leq T \leq 10^9\)
- \(1 \leq L \leq 10^7\)
- \(1 \leq x_i \leq L\)
- \(1 \leq y_i \leq 4\)
Output
Output one line containing the number of marbles that will be released in the first \(T\) seconds.