Snow Plowing
시간 제한1초메모리 제한1024 MB
길이 L인 도로 위 여러 지점에 주차된 제설차가 분당 1km로 움직이며 T분 안에 도로 전체를 제설하고 복귀할 때 최소 비용을 구한다.
문제
There has been snowing heavily last night. Prienai snow plowing company now faces a huge challenge – it has to clean L kilometers of snow-covered road.
The company owns N snow plowers numbered from 1 to N. Initially, i-th snow plower is parked in a garage located at the Ai-th kilometer of the road. It costs Ki euros for the i-th snow plower to drive one kilometer.
After finishing the work all snow plowers must return to the garages they left from. In order to avoid traffic jams they have to finish plowing and return to garages within T minutes.
Every vehicle can drive at most 1 kilometer per minute, regardless of whether it is plowing or not.
Calculate the lowest possible cost for cleaning the snow off the entire road.
입력
The first row contains three integers: the number of snow plowers N, the length of the road L, the duration in minutes T in which the road has to be cleaned and the snow plowers have to get back to their garages.
N rows follow, i-th of which contains two integers: Ai, the distance from the beginning of the road to the i-th garage, and Ki – the cost of driving one kilometer for that snow plower. All garage coordinates are presented in strictly ascending order (Ai < Ai+1 for every i).
출력
Output a single number – the lowest possible cost of cleaning the road. If it is impossible to clean the road in T minutes output the word NEPAVYKS.
제한
- 1 ≤ N, L ≤ 10 000
- 1 ≤ T ≤ 1 000
- 0 ≤ Ai ≤ L
- 0 ≤ Ki ≤ 1 000