27940번 - 가지 산사태 스페셜 저지

문제

키위는 맛있는 가지를 직접 기르기 위해 주말농장에 가지를 심기로 하였다. 농장은 총 $N$층으로 구성되어 있으며 제일 낮은 곳이 1ドル$층, 제일 높은 곳이 $N$층이다. 산비탈에 위치한 농장에서 즐겁게 가지를 기르던 차에 폭우 소식이 들려왔다. 땅이 경사져 비가 많이 오면 흙이 쓸려 내려가서 농사를 망칠 수도 있다!

기상 예보에서 비를 맞는 층과 그 양을 확인할 수 있었다. 비는 총 $M$번 쏟아지며, $i$번째 비가 오는 순간 농장의 1ドル$층부터 $t_i$층이 동시에 빗물을 각각 $r_i$만큼 받게 된다. 날이 매우 습해 땅에 스며든 빗물은 증발하지 않는다. 따라서 각 층이 받은 빗물의 양은 마지막 비가 내린 직후까지 누적된다.

농장의 각 층은 최대 $K$만큼의 빗물을 받아도 쓸려 내려가지 않는다. 만약 어떤 층에 누적된 빗물의 양이 $K$를 초과한다면 해당 층은 무너진다. 비가 와서 무너지는 층이 동시에 여러 곳 발생할 수도 있다.

농장의 한 층이라도 무너지기 전에 가지를 모두 수확하려고 한다. 몇 번째 비가 온 직후 어떤 층이 무너지는지 예측해 보자.

입력

첫째 줄에 농장의 층수 $N,ドル 비가 오는 횟수 $M,ドル 각 층이 버틸 수 있는 빗물의 양을 나타내는 정수 $K$가 주어진다. $(1 \le N \le 10^5;$ 1ドル \le M \le 10^6;$ 1ドル \le K \le 2 \times 10^9)$

둘째 줄부터 $M$개의 줄에 걸쳐 각 줄에 비의 정보를 나타내는 정수 $t_i$와 $r_i$가 주어진다. $(1 \le t_i \le N;$ 1ドル \le r_i \le 10^9)$

모든 $r_i$의 합은 2ドル \times 10^9$를 초과하지 않는다.

출력

$i$번째 비가 온 직후 처음으로 무너지는 층이 발생할 때, 첫째 줄에 $i$와 무너지는 층을 아무거나 하나 출력한다.

모든 비가 온 후에 어떤 층도 무너지지 않는다면 -1을 출력한다.

제한

힌트