주유하기

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

요약

탱크 용량이 정해진 차로 거리 d를 이동할 때 기름이 떨어지지 않도록 가장 적은 수의 주유소를 골라 정차 횟수의 최솟값을 구한다. 불가능하면 -1을 출력한다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬, 배열
정답자: 아직 제출이 없습니다

문제

자동차로 먼 거리를 여행하려고 한다. 도중에 연료가 떨어지지 않도록 하면서, 주유를 위해 멈추는 횟수를 최대한 적게 하는 주유소들을 골라야 한다.

자동차의 연료 탱크 용량은 $n$ 리터이고, $1$ km를 달릴 때마다 $0.1$ 리터의 연료를 사용한다. 따라서 연료를 가득 채운 탱크로는 최대 $10n$ km를 달릴 수 있다. 자동차는 연료 탱크를 가득 채운 상태로 출발한다.

경로를 따라 $m$ 개의 주유소가 있으며, 각 주유소마다 출발점으로부터의 거리와 연료 가격이 정해져 있다. 목표 지점은 출발점에서 $d$ km 떨어져 있다.

도중에 연료가 떨어지지 않고 목표 지점까지 도착할 수 있으면서, 주유를 위해 멈추는 횟수가 최소가 되는 주유소들의 집합을 구하시오.

입력

첫째 줄에 세 정수 $n$ , $m$ , $d$ 가 주어진다. 각각 연료 탱크의 용량(리터), 경로에 있는 주유소의 개수, 여행의 총 거리(km)이며, $0 < n \le 100$ , $0 \le m \le 100000$ , $0 \le d \le 100000$ 을 만족한다.

이어지는 $m$ 개의 줄에는 각각 두 정수가 주어지는데, 출발점에서 그 주유소까지의 거리(km)와 그 주유소의 연료 가격(리터당, $1$ 센트의 $10$ 분의 $1$ 을 단위로)이다.

자동차는 연료 탱크를 가득 채운 상태로 출발하며, $1$ km를 달릴 때마다 $0.1$ 리터의 연료를 사용한다.

출력

연료가 떨어지지 않도록 주유하며 멈추는 주유소들의 최적 집합에 대해, 그 집합에 속한 주유소의 개수(즉 멈추는 최소 횟수)를 정수 하나로 출력한다. 연료가 떨어지지 않고서는 여행을 마칠 수 없다면 $-1$ 을 출력한다.

예제3

예제 1
입력
```
50 2 1000
500 1293
750 1337
```
예상 출력
```
1
```
예제 2
입력
```
10 0 100
```
예상 출력
```
0
```
예제 3
입력
```
5 1 200
100 900
```
예상 출력
```
-1
```