디아나와 황금 사과

로마의 사냥꾼 디아나는 달리기가 빠르다. 디아나는 달리기 경주에서 자신을 이기거나 자신과 같은 기록을 낸 남자와 결혼하겠다고 약속했다. 트로이의 왕자 험퍼동키는 이 경주에서 이기려고 트랙 곳곳에 황금 사과를 놓아 두었다. 디아나가 사과를 줍느라 느려질 것이라고 본 것이다. 그러나 디아나는 지금 누구와도 결혼할 생각이 없고, 험퍼동키라면 더욱 그렇다. 디아나는 이기면서 주울 수 있는 금의 무게를 정확히 계산한다. 당신은 디아나가 되어 독신을 지키면서 금을 최대한 많이 챙겨야 한다.

경주 거리는 100 m 단위로 $L$이다. 아무것도 들지 않은 디아나는 100 m를 $T_d$초에 달리고, 험퍼동키는 100 m를 $T_h$초에 달린다. 험퍼동키는 사과를 줍지 않는다.

$i$번 사과는 출발점에서 100 m 단위로 $x_i$만큼 떨어진 지점에 있고, 무게는 $w_i$ kg이다. 디아나는 주울 사과를 마음대로 고를 수 있고, 한 번 주운 사과는 결승선까지 들고 간다. 사과를 줍는 데는 시간이 걸리지 않는다. 금을 1 kg 들 때마다 100 m마다 $d$초가 더 걸리므로, $i$번 사과를 주우면 총 기록이 $d \times w_i \times (L - x_i)$초 늘어난다.

디아나가 사과 집합 $S$를 주웠다면 디아나의 기록은 $L \times T_d + \sum_{i \in S} d \times w_i \times (L - x_i)$초이고, 험퍼동키의 기록은 $L \times T_h$초이다. 디아나는 자기 기록이 험퍼동키의 기록보다 작을 때만 이긴다. 두 기록이 같으면 결혼해야 한다.

디아나가 이기면서 결승선을 통과할 때 들고 있을 수 있는 금의 최대 무게를 구하라.

첫째 줄에 정수 다섯 개 $L$, $T_d$, $T_h$, $N$, $d$가 공백으로 구분되어 주어진다. ($1 \le L \le 1000$, $10 \le T_d \le 30$, $10 \le T_h \le 30$, $0 \le N \le 1000$, $0 < d \le 10$)

다음 $N$개의 줄에 사과 하나씩, 정수 두 개 $w_i$와 $x_i$가 공백으로 구분되어 주어진다. ($0 < w_i \le 50$, $0 \le x_i < L$)

여러 사과가 같은 지점에 놓여 있을 수 있다.

디아나가 험퍼동키보다 먼저 결승선을 통과하면서 들고 있을 수 있는 금의 최대 무게 $W$를 한 줄에 출력한다. 디아나가 험퍼동키를 이길 수 없으면 대신 다음 줄을 출력한다.

Diana marries Humperdonkey