12842번 - 튀김 소보루

영선이는 대전에 내려갔다 서울 오는 길에 튀김 소보루 n개를 사왔다. (1 ≤ n ≤ 100,000)

영선이가 SCCC 회원들에게 나누어 주기 위하여 001에 두고 잠깐 나갔다 온 사이에 온전한 튀김 소보루는 s개가 남아 있었다.(먹기 위해 집어 든 튀김소보루는 제외한다)

영선이가 자리를 비운 동안 001에는 m명이 있었고, 각 사람은 1부터 m번까지 번호가 매겨져 있다. 영선이는 평소에 SCCC 회원들과 식사를 자주해서 식사 속도를 알고 있다. 이를 바탕으로 튀김 소보루 1개를 먹는데 걸리는 시간을 유추할 수 있다.

영선이를 위해 이 정보들을 바탕으로 마지막으로 튀김 소보루를 집어 든 사람의 번호를 구하여라.

여러 사람이 동시에 소보루를 집는다면 번호가 작은 사람이 먼저 잡으며, 영선이가 떠나자 마자 바로 먹기를 시작한다.

예를 들어, 소보루를 먹는 시간이 1번은 1초, 2번은 3초, 3번은 5초에 하나씩 먹는다고 하고, 소보루는 1000개 있다고 하자.

• 1개가 줄었다면 1번 사람이 처음 빵을 집을 것이다.
• 2개가 줄었다면 2번 사람이 1번 사람이 집은 직후 처음 빵을 집을 것이다.
• 3개가 줄었다면 3번 사람이 2번 사람이 집은 직후 처음 빵을 집을 것이다.
• 4개가 줄었다면 1번 사람이 빵을 다 먹고, 2개째 빵을 집을 것이다.
• 5개가 줄었다면 1번 사람이 빵을 다 먹고, 3개째 빵을 집을 것이다.
• 6개가 줄었다면 1번 사람이 빵을 다 먹고, 4개째 빵을 집을 것이다.
• 7개가 줄었다면 2번 사람이 빵을 다 먹고 1번 사람이 집은 직후, 2개째 빵을 집을 것이다.

첫 번째 줄에 n s 가 주어진다. n은 영선이가 사온 튀김 소보루의 개수이다.

s는 영선이가 돌아왔을 때 남아 있던 튀김 소보루의 개수이다. (0 ≤ s ≤ n-1)

두 번째 줄 에는 m (1 ≤ m ≤ 100,000) 이 주어지고 , 다음 m 개의 줄 에는 1번부터 m번까지의 사람이 한 개의 소보루를 먹는데 걸리는 시간 t_i(초) 가 주어진다. (1 ≤ t_i ≤ 1,000)

마지막으로 소보루를 집어 든 사람의 번호를 출력한다.