Diana and the Golden Apples

The Roman huntress Diana runs fast. She has agreed to marry any man who beats her in a race, or even matches her time. Prince Humperdonkey of Troy plans to win by leaving golden apples along the track, betting that Diana will slow herself down picking them up. Diana wants to marry nobody at present, and Humperdonkey least of all, and she works out exactly how much gold she can carry and still win. You are Diana. Stay single and collect as much gold as you can.

The race is $L$ units of 100 m long. Carrying nothing, Diana runs 100 m in $T_d$ seconds, and Humperdonkey runs 100 m in $T_h$ seconds. Humperdonkey never picks up an apple.

Apple $i$ lies $x_i$ units of 100 m from the start and weighs $w_i$ kg. Diana chooses freely which apples to pick up, and she carries every apple she picks up all the way to the finish line. Picking up an apple takes no time. Each kilogram of gold she carries costs her $d$ extra seconds per 100 m, so picking up apple $i$ adds $d \times w_i \times (L - x_i)$ seconds to her total time.

If Diana picks up the set of apples $S$, her time is $L \times T_d + \sum_{i \in S} d \times w_i \times (L - x_i)$ seconds and Humperdonkey's time is $L \times T_h$ seconds. Diana wins only when her time is smaller than his. Equal times mean she has to marry him.

Find the largest total weight of gold Diana can be carrying when she crosses the finish line and still wins.

The first line contains five space separated integers $L$, $T_d$, $T_h$, $N$ and $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$)

Each of the next $N$ lines describes one apple with two space separated integers $w_i$ and $x_i$. ($0 < w_i \le 50$, $0 \le x_i < L$)

Several apples can lie at the same point.

Print on one line the largest weight of gold $W$ that Diana can be carrying while she finishes ahead of Prince Humperdonkey. If Diana cannot beat Humperdonkey, print the following line instead.

Diana marries Humperdonkey