Miss That Bus and You Are Late!!

Interview

Time limit1sMemory limit512 MB

Summary

Simulate a single-lane bus stop where each bus parks in the frontmost free spot, waits if a bus ahead is still parked, and departs after its dwell time; report the parking spot of the m-th bus.

Level: Medium5 of 10
Topics: Simulation, Queue, Implementation
Solved: No attempts yet

Problem

Youngwoo commutes by bus from Suwon to Seoul every day. His bus is so crowded that arriving a little late can mean being pushed aside and left behind, and the interval between buses is so long that missing one means being late for class. So today he wants to compute in advance where his bus will stop and wait at that spot.

The bus stop is a straight single-lane passage. Spots are numbered 1, 2, ..., $n$ from the front in the direction of travel, and at most $n$ buses can be parked at the same time. The stop display shows each bus arrival time in minutes and dwell time in minutes for passenger boarding. To prevent congestion inside the stop, buses enter and leave under the following rules.

Because the stop is a single lane, a bus behind can never overtake a bus ahead. Even a rear bus whose dwell time has ended waits at that minute if any bus is still parked ahead of it, including when the bus ahead departs at the same minute.
A bus arriving at the stop entrance parks at the frontmost empty spot. If every spot is occupied, it waits outside the entrance in a single line in arrival order.
At every minute mark, departing buses leave first, then the buses waiting or just arriving enter one by one in arrival order, each taking the frontmost free spot. Buses move so fast that this whole process is assumed to take 0 time. For example, suppose bus A arrives at minute 1, parks at spot 1 for 2 minutes, bus B arrives at minute 3, and there are no other buses. Then at the moment minute 3 begins, bus A leaves first and bus B enters and parks at spot 1.

Dwell time is counted from the moment a bus actually parks. Time spent waiting outside the entrance does not count toward it.

Input

The first line gives $n$ , the number of buses that can park at the same time, and $m$ , the number of buses up to and including the bus Youngwoo wants to ride ( $1 \le n \le 10$ , $1 \le m \le 100$ ).

Each of the next $m$ lines gives the arrival time $t$ and the dwell time $p$ of one bus, in arrival order. Buses arriving at the same minute are treated as arriving in input order ( $1 \le t \le 100$ , $1 \le p \le 10$ , $t_i \le t_{i+1}$ ).

Output

Print, on one line, the spot number where the bus Youngwoo wants to ride (that is, the $m$ -th bus) parks.

Examples5

Example 1
Input
```
2 3
1 1
2 1
3 1
```
Expected output
```
1
```
Example 2
Input
```
2 3
1 2
2 1
3 1
```
Expected output
```
1
```
Example 3
Input
```
2 3
1 1
2 2
3 1
```
Expected output
```
2
```
Example 4
Input
```
2 3
1 2
1 2
3 1
```
Expected output
```
1
```
Example 5
Input
```
2 3
1 4
2 1
3 1
```
Expected output
```
1
```