The world famous "Jacky Jewels" had been robbed yet again! With no help from the police, Jacky has asked you for help.

The jewel store consists of $N$ jewels arranged in a circle, where the $i$-th jewel is to the left of the $i+1$-th jewel and the $N$-th jewel is to the left of the first jewel.
The $i$-th jewel has a value of $i$ and an identical weight of $B$ for $1\leq i \leq N$.

From reliable sources, you know that the same thieves are going to rob your store tonight.
From your recent encounter, you know that there are $M$ thieves in total, and each thief steals exactly $K$ consecutive jewels.
No two thieves will steal the same jewel.
It is not known which jewels the thieves will steal.

You luckily have $T$ types of counterfeit jewels, you have $A[i]$ jewels of the $i$-th type and all jewels of the $i$-th type have $W[i]$ weight.
All counterfeit jewels have no value.
No two types have the same weight.
You would like to switch some of the real jewels with counterfeit ones to minimize your losses.

However, you know that the thieves are careful, and they would compare the sum of weights of the jewels they stole with each other.
Formally, let $S[i]$ be the sum of weights of jewels the thief $i$ stole. You should ensure that $S[i] = S[j]$ for all $1 \leq i, j \leq M$ for all possible situations.

Time is running out and Jacky would like to know the minimum sum of values of jewels of all the thieves in the worst case situation.
Can you help Jacky?

Input

The first line contains 5 integers: $N, M, K, B, T$.
The next $T$ lines contain 2 integers each: $A[i], W[i]$.

Output

Output a single integer, the minimum sum of values in the worst case.

Constraints

• $1\leq N, K, B, A[i], W[i]\leq 10^9$
• $2 \leq M \leq 10^9$
• $1 \leq T \leq 10^5$
• $K\times M \leq N$

Subtask 1 (10%): $K=1$
Subtask 2 (20%): $N\leq 10^6, W[i] \neq B$
Subtask 3 (30%): $N$ is divisible by $K, W[i] \neq B$
Subtask 4 (20%): $W[i] \neq B$
Subtask 5 (20%): No additional constraints