There are houses belonging to the JOI Chairman K and the former Chairman M on a long, straight road. IOI-kun, a koala who is good at jumping, is planning to go from Chairman K's house to former Chairman M's house.

This road is considered a number line, and each location is represented by a coordinate as a single number. The coordinate of Chairman K's house is $K$, and the coordinate of former Chairman M's house is $M$. There are $N$ houses of JOI tutors between them, and the coordinate of the $i$-th tutor's house is $T_i$.

IOI-kun starts at Chairman K's house with 0 stamina and makes several jumps to reach former Chairman M's house. In one jump, he can move a distance $d$ in the direction of former Chairman M's house, where $d$ must be an integer satisfying $1 \le d \le D$. Each jump reduces IOI-kun's stamina by $A$ (stamina can become a negative value).

If there is a tutor's house at the location where IOI-kun lands after a jump, he can stay at that house exactly once. When he stays at the $i$-th tutor's house, his stamina increases by $B_i$.

IOI-kun wants to arrive at former Chairman M's house with as much stamina as possible.

Task

Write a program that calculates the maximum possible stamina value when IOI-kun arrives at former Chairman M's house.

Input

Read the following input from standard input:

• The first line contains integers $K, M, D, A, N$ separated by spaces, representing the coordinate of Chairman K's house, the coordinate of former Chairman M's house, the maximum distance he can jump in one jump, the stamina lost per jump, and the number of tutor houses, respectively.
• The $i$-th line (for $1 \le i \le N$) of the following $N$ lines contains two integers $T_i, B_i$ separated by spaces, representing the coordinate of the $i$-th tutor's house and the stamina gained when staying at the $i$-th tutor's house.

Output

Output the maximum possible stamina value as an integer when IOI-kun arrives at former Chairman M's house on a single line to standard output.

Constraints

All input data satisfies the following conditions:

• $1 \le D \le 1\,000\,000\,000$.
• $1 \le A \le 1\,000\,000\,000$.
• $1 \le N \le 100\,000$.
• $0 \le K < T_1 < \dots < T_N < M \le 1\,000\,000\,000$.
• $1 \le B_i \le 1\,000\,000\,000$ ($1 \le i \le N$).

Subtasks

Subtask 1 [20 points]

• $N \le 1\,000$ is satisfied.

Subtask 2 [30 points]

• $D \le 100$ is satisfied.

Subtask 3 [50 points]

• There are no additional constraints.

Examples

Input 1

0 10 4 10 2
3 10
8 5

Output 1

-20

Note 1

In this example, an optimal sequence of actions for IOI-kun is as follows:

• Jump a distance of 3. IOI-kun lands at coordinate 3, and his stamina becomes $-10$.
• Stay at the 1st tutor's house. His stamina becomes 0.
• Jump a distance of 4. IOI-kun lands at coordinate 7, and his stamina becomes $-10$.
• Jump a distance of 3. IOI-kun arrives at former Chairman M's house, and his stamina becomes $-20$.

Input 2

3 42 9 10 8
10 5
12 9
26 7
27 2
30 8
34 6
36 8
40 10

Output 2

-25

Note 2

In this example, an optimal sequence of actions for IOI-kun is as follows:

• Jump a distance of 9. IOI-kun lands at coordinate 12, and his stamina becomes $-10$.
• Stay at the 2nd tutor's house. His stamina becomes $-1$.
• Jump a distance of 9. IOI-kun lands at coordinate 21, and his stamina becomes $-11$.
• Jump a distance of 9. IOI-kun lands at coordinate 30, and his stamina becomes $-21$.
• Stay at the 5th tutor's house. His stamina becomes $-13$.
• Jump a distance of 6. IOI-kun lands at coordinate 36, and his stamina becomes $-23$.
• Stay at the 7th tutor's house. His stamina becomes $-15$.
• Jump a distance of 6. IOI-kun arrives at former Chairman M's house, and his stamina becomes $-25$.