Informatica Online Judge

  휴식 장소(Silver) [2189 / 088D]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 8   Total Tried : 9


The Champion of this Problem (C++) : t1234 - 0ms / 333byte
My Best Submission (C++) : N/A

[USACO 2018(Dhruv Rohatgi)]

Background

농부 존과 개인 트레이너 젖소인 베시가 반카우버 산을 함께 등산해 올라가려고 한다.

등산은 L미터 길이의 긴 직선 등산로를 따라 올라가는 것처럼 생각할 수 있는데, 존은 미터당 $r_F$의 일정한 속도로 등산하게 될 것이다.
존은 매우 튼튼하기 때문에, 중간에 있는 휴식 장소에서 쉬지 않는다.

하지만, 베시는 휴식 장소에서 잠시 쉬며 맛있는 풀을 뜯을 수 있다. 그렇다고 아무 휴식 장소에서나 쉬는 것은 아니다!

등산로에는 N개의 휴식 장소가 있다.; i번째 휴식 장소는 등산로 시작 후 $x_i$위치에 있으며,
그 곳에는 $c_i$ 만큼 맛있는 풀이 있다. 베시가 i번째 장소에서 $t$초 쉬면, $c_i$*$t$ 만큼 얻을 수 있다.

휴식 장소에서 쉬지 않으면, 베시는 미터당 $r_B$의 일정한 속도로 등산하게 될 것이다.
물론 베시는 젊고 건강하기 때문에, $r_B$는 $r_F$보다 반드시 크다.(농부 존 보다 더 빠르다.)

베시는 맛있는 풀을 최대한 많이 뜯고 싶어한다. 하지만 농부 존을 생각해 준다.; 등산 도중에 베시가 존 보다 뒤에 있게되면,
존이 등산하는 동기를 잃게 될 수도 있기 때문이다!

등산하는 도중에 농부 존 보다 뒤쳐지지 않으면서, 얻을 수 있는 풀의 최대량을 알아보자.

Input

첫 번째 줄에 L, N, $r_F$, $r_B$ 가 공백을 두고 입력된다.
그 다음 N개의 줄에는 i번째 휴식 장소에 대한 정보 $x_i$와 $c_i$가 공백을 두고 입력된다.

[입력값의 정의역]
$1≤L≤1,000,000$
$1≤$$r_B$<$r_F$$≤1,000,000$
$1≤N≤100,000$
$0$<$x_i$<$L$
$1≤$ $c_i$ $≤1,000,000$
$1≤$ $r_B$ $≤1,000,000$

Output

베시가 얻을 수 있는 풀의 최대량을 출력한다.

IO Example

입력
10 2 4 3
7 2
8 1

출력
15

* 설명 :
x=7 인 휴식 장소에서 7초 동안 쉰 후(14만큼 풀을 얻는다), x=8인 휴식 장소에서 1초 동안 쉬면 된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]