학원 연습 점수 정정장

문제

한 학원에서는 학생들의 연습 활동을 점수로 기록한다. 학생에게는 1번부터 N번까지 서로 다른 번호가 붙어 있으며, 처음 기록된 점수는 학생 번호 순서대로 보관되어 있다. 담당 강사는 기록을 확인하다가 빠뜨린 활동이나 잘못 반영한 활동을 발견하면 정정장에 변경 내역을 한 줄씩 적는다. 프로그램은 이 정정장을 모두 반영한 뒤 가장 높은 점수를 가진 학생을 찾아야 한다. 변경 내역 한 줄에는 학생 번호와 점수 변화량이 적혀 있다. 변화량이 양수이면 해당 학생의 현재 점수에 그 값을 더하고, 음수이면 그 값의 절댓값만큼 뺀다. 변화량이 0이면 점수가 그대로 유지된다. 정정장에 적힌 값은 새로운 점수 자체가 아니라 현재 점수에 더할 값이라는 점에 주의해야 한다. 한 줄의 변경 내역은 적힌 번호의 학생 한 명에게만 영향을 준다. 같은 학생의 변경 내역이 여러 번 등장할 수 있다. 이 경우 등장한 모든 변화량을 빠짐없이 반영한다. 어떤 학생은 정정장에 한 번도 등장하지 않을 수도 있으며, 그런 학생의 점수는 처음 점수와 같다. 정정장은 입력된 순서대로 처리한다. 처리 도중 점수가 음수가 되어도 그대로 보관하며, 점수를 0으로 올리거나 별도의 최솟값으로 제한하지 않는다. 마지막 점수에도 같은 규칙을 적용한다. 모든 변경 내역을 반영한 뒤의 점수를 최종 점수라고 한다. 최종 점수가 가장 높은 학생을 한 명 선정한다. 가장 높은 점수를 가진 학생이 여러 명이면 학생 번호가 가장 작은 학생을 선정한다. 학생은 적어도 한 명 있으므로 선정할 학생이 없는 경우는 없다. 선정된 학생의 번호와 그 학생의 최종 점수를 구한다. 중간 처리 단계에서 가장 높은 점수를 가진 학생은 결과에 영향을 주지 않는다.

입력

첫째 줄에 학생 수 N과 변경 내역 수 M이 공백으로 구분되어 주어진다. 둘째 줄에 1번부터 N번 학생의 처음 점수 A1, A2, …, AN이 주어진다. 다음 M개 줄에 학생 번호 P와 점수 변화량 D가 주어진다. 모든 값은 정수이며 1 ≤ N ≤ 1,000, 0 ≤ M ≤ 1,000, 0 ≤ Ai ≤ 1,000, 1 ≤ P ≤ N, -1,000 ≤ D ≤ 1,000이다. M이 0이면 변경 내역 줄은 주어지지 않는다.

출력

선정된 학생의 번호와 최종 점수를 공백으로 구분하여 출력한다. 최종 점수가 같은 학생이 여러 명이면 번호가 가장 작은 학생을 출력한다. 최종 점수가 음수이면 음수 부호를 포함하여 출력한다.

4 3
10 8 10 4
2 5
1 -2
4 9

2 13

3 0
7 7 2

1 7

2 3
0 1
1 -5
2 -8
2 2

1 -5

출처: Devin.KR 자체 제작