시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 205 72 53 35.570%

문제

영우는 6년간 매일 수원에서 서울까지 버스로 통학하는 프로통학러다. 영우가 타는 광역버스는 이용객이 너무 많아 잘못하면 사람에 밀려 못 탈수도 있고, 배차시간이 너무 길어 버스를 놓치고 강의에 지각한 적이 한두번이 아니다. 잦은 지각으로 출석점수에 위기를 느낀 영우는 오늘만은 자신의 버스가 정차할 위치를 미리 계산해서 그 자리에 미리 줄을 서려고 한다. 당신의 임무는 영우를 위해 영우가 탈 버스의 정차 위치를 미리 계산해주는 것이다. 

버스 정류장은 1차선 통로 모양으로, 진행방향의 맨 앞부터 1번, 2번, n번 위치까지 총 n대의 버스가 동시에 정차해 있을 수 있다. (그림1) 정류장 알림판에는 각 버스의 도착시각(분)과 승객들의 탑승을 위해 몇 분간 정차해 있을지 정차시간(분)이 안내 된다. 또한, 정류장 내 교통 혼잡을 막기 위해 버스들은 다음과 같은 규칙에 따라 정류장에 들어오고 나간다.

  1. 버스 정류장은 1차선 통로이기 때문에, 뒤의 버스는 앞의 버스를 추월할 수 없다. 즉 뒤에 정차한 버스는 자신의 정차시간이 다 끝나도 앞에 정차해 있는 버스가 모두 떠날 때까지 출발할 수 없다.
  2. 정류장 입구에 도착한 버스는 자신이 정차할 수 있는 위치 중 가장 앞쪽에 정차한다. 만약 n번 위치에 다른 버스가 정차해 있어 들어갈 수 없다면, 정류장 입구에 도착한 순서대로 일렬로 대기한다. (그림2)

  1. 매 분 단위 시각에 정류장 내 버스들은 다음과 같은 순서로 이동한다. 떠나는 버스들은 자신의 위치부터 맨 앞 출구 사이에 장애물(즉, 아직 정차시간이 끝나지 않아 더 정차해 있어야 하는 버스)이 없다면 앞에서부터 차례차례 출구로 빠져나간다. 그런 다음, 이 시각 입구에 대기하고 있거나 막 도착한 버스들이 도착한 순서대로 차례차례 진입하여 가능한 맨 앞자리에 정차한다. 버스들의 속도는 무한대에 가까워서 이 과정에 소요되는 시간, 즉 떠나는 버스들이 모두 빠져나가고 도착한 버스들이 모두 정차하는 순간까지 걸린 시간은 0이라고 가정한다. 예를 들어, 버스 A는 1분에 도착해 1번 위치에 2분 동안 정차하고, 버스 B는 3분에 도착하고, 다른 버스들은 없다고 가정하자. 그러면 3분이 되는 순간, 버스 A가 먼저 정류장을 빠져나가고 버스 B가 입구로 들어와 가능한 위치 중 가장 앞쪽인 1번 위치에 정차하게 된다.

입력

프로그램의 입력은 표준 입력으로 받는다. 첫줄에는 정류장에 동시에 정차 가능한 버스 수 n, 영우가 타려는 버스까지의 버스 수 m이 주어진다.(1 ≤ n ≤ 10, 1 ≤ m ≤ 100)

다음 m줄에는 각 버스가 정류장에 도착하는 시간 t와 정차하고 있는 시간 p가 버스가 도착하는 순서대로 주어진다. 만약 여러 버스가 같은 시각에 도착한다면 입력에 주어진 순서대로 버스가 도착한 것으로 본다. (1 ≤ t ≤ 100, 1 ≤ p ≤ 10, ti ≤ ti+1)

출력

프로그램의 출력은 표준 출력으로 한다. 영우가 타려는 버스(즉, m번째 버스)가 정류장의 어느 위치에 정차하는지 구하시오.

예제 입력 1

2 3
1 1
2 1
3 1

예제 출력 1

1

예제 입력 2

2 3
1 2
2 1
3 1

예제 출력 2

1

예제 입력 3

2 3
1 1
2 2
3 1

예제 출력 3

2

예제 입력 4

2 3
1 2
1 2
3 1

예제 출력 4

1

예제 입력 5

2 3
1 4
2 1
3 1

예제 출력 5

1

예제 입력 6

2 5
1 10
2 10
3 1
4 10
5 1

예제 출력 6

1