가지 산사태

시간 제한1초메모리 제한1024 MB

요약

각 비가 1층부터 t_i층에 r_i씩 더할 때, 누적 빗물이 처음으로 K를 넘는 층과 그 비의 번호를 출력한다.

난이도: 보통10점 중 7점
유형: 세그먼트 트리, 연결 리스트, 이분 탐색, 누적 합
정답자: 아직 제출이 없습니다

문제

키위는 맛있는 가지를 직접 기르기 위해 주말농장에 가지를 심기로 하였다. 농장은 총 $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을 출력한다.

예제3

예제 1
입력
```
5 4 5
3 3
2 2
5 1
2 3
```
예상 출력
```
3 2
```
예제 2
입력
```
5 4 8
2 2
1 1
4 3
5 2
```
예상 출력
```
-1
```
예제 3
입력
```
10 3 10
3 1
4 20
1 2
```
예상 출력
```
2 3
```