주유하기

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

자동차의 연료 탱크 용량은 $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$을 출력한다.