변경 기록 뒤의 항공권

문제

항공권 예약 화면에는 N개의 항공편이 1번부터 N번까지 번호순으로 표시되어 있다. 각 항공편에는 지금 새로 예약할 수 있는 좌석 수가 적혀 있다. 예약 담당자는 화면을 연 뒤 도착한 변경 기록 Q개를 모두 반영하고, 마지막에 예약 가능한 좌석이 가장 많이 남은 항공편 하나를 화면 맨 위에 추천하려고 한다. 변경 기록 하나는 항공편 번호 p와 좌석 수의 변화량 d로 이루어진다. d가 양수이면 예약 취소 등으로 인해 p번 항공편에서 예약 가능한 좌석이 d개 늘어난다. d가 음수이면 새 예약으로 인해 예약 가능한 좌석이 -d개 줄어든다. d가 0이면 좌석 수는 그대로이다. 각 기록은 지정된 항공편 하나에만 적용하며, 다른 항공편의 좌석 수에는 영향을 주지 않는다. 변경 기록은 입력에 주어진 순서대로 모두 적용한다. 같은 항공편 번호가 여러 기록에 등장할 수 있으므로, 그 항공편의 이전 변경 결과를 이어서 사용해야 한다. 어떤 항공편은 변경 기록에 한 번도 등장하지 않을 수도 있다. 이러한 항공편은 처음 주어진 예약 가능 좌석 수를 마지막까지 유지한다. 입력은 모든 기록을 차례로 반영하는 동안 각 항공편의 좌석 수가 항상 정해진 범위 안에 있도록 주어진다. 모든 변경을 마친 뒤 예약 가능한 좌석이 가장 많은 항공편을 선택한다. 가장 많은 좌석 수가 같은 항공편이 여러 개이면 번호가 가장 작은 항공편을 선택한다. 단, 모든 항공편의 예약 가능 좌석 수가 0이면 추천할 항공편이 없으므로 0을 출력한다. 변경 기록이 하나도 없을 수도 있으며, 이때에는 처음 주어진 좌석 수만으로 같은 선택 규칙을 적용한다. 최종적으로 추천할 항공편의 번호를 구한다.

입력

첫째 줄에 항공편의 수 N과 변경 기록의 수 Q가 공백으로 구분되어 주어진다.
둘째 줄에 1번부터 N번까지 각 항공편의 초기 예약 가능 좌석 수가 공백으로 구분되어 주어진다.
다음 Q개의 줄에는 항공편 번호 p와 변화량 d가 공백으로 구분되어 주어진다.
모든 입력값은 정수이다. 1 ≤ N ≤ 1,000, 0 ≤ Q ≤ 1,000, 1 ≤ p ≤ N, -1,000 ≤ d ≤ 1,000이다. 초기 좌석 수와 각 변경을 적용한 직후의 모든 좌석 수는 0 이상 1,000 이하이다.

출력

모든 변경 기록을 반영한 뒤 예약 가능한 좌석이 가장 많은 항공편의 번호를 출력한다. 동점이면 가장 작은 번호를 출력한다. 모든 항공편의 좌석 수가 0이면 0을 출력한다.

4 3
3 8 2 6
2 -5
3 4
4 -1

3

3 2
4 1 4
2 3
1 0

1

2 2
2 0
1 -2
2 0

0

출처: Devin.KR 자체 제작