U, Our Star!

Interview

Time limit1sMemory limit1024 MB

Summary

Given products with limited counts and prices, find the smallest payment that maximizes points, where points are floor(payment / X) times Y, capped at D.

Level: Medium5 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

The Seoul City University cafe sells various Iruemae goods that can only be bought with U, Our Star! points.

The cafe runs the following event.

For every $X$ won spent at the cafe, you receive $Y$ of U, Our Star! points.
The maximum number of U, Our Star! points you can receive is $D$ .

Alimi loves cute Iruemae goods and wants to collect as many U, Our Star! points as possible during this event. Alimi has enough money to buy any products as many times as desired. However, Alimi dislikes overspending, so Alimi wants to pay the smallest amount among the payments that maximize the points.

Given the products as pairs of available quantity and price, find the minimum payment that maximizes the U, Our Star! points received.

Input

The first line contains three positive integers $X$ , $Y$ , and $D$ .

$1 \le Y < X \le 100000$
$D$ is a positive multiple of $Y$ , and $D \div Y \times X \le 100000$ .

The second line contains the number of products $N$ . ( $1 \le N \le 100$ )

Each of the next $N$ lines contains the available quantity $a$ and the price $b$ of a product, separated by a space. ( $1 \le a \le 100$ , $1 \le b \le 100000$ )

The total available quantity of all products is between 1 and 100, inclusive.

Output

Print the minimum payment that maximizes the U, Our Star! points received.

If you cannot receive any U, Our Star! points even after buying all products, print $0$ .

Examples2

Example 1
Input
```
10 1 5
2
1 5
4 10
```
Expected output
```
40
```
Example 2
Input
```
10 1 5
4
1 5
4 10
1 11
1 12
```
Expected output
```
51
```