Triangular Gimbap Price Comparison

Interview

Time limit1sMemory limit128 MB

Summary

Given several price rates for gimbap, compute the cheapest cost to buy exactly 1000 grams using the best per-gram rate among all stores.

Level: Easy2 of 10
Topics: Math, Greedy, Implementation
Solved: No attempts yet

Problem

Sanggeun and Jeongin want to buy 1,000 grams of triangular gimbap as cheaply as possible from several convenience stores.

Each store displays its price in the form "X won for Y grams". The first line gives the price at the reference store, followed by the prices at N other stores.

They may buy all 1,000 grams from one store or split the purchase across multiple stores. They cannot buy from any store other than the reference store and the N listed stores.

Compute the minimum amount of money needed to buy 1,000 grams.

Input

The first line contains X and Y, the price information for the reference store. This means X won for Y grams. (1 ≤ X ≤ 100, 1 ≤ Y ≤ 1,000)

The second line contains N, the number of other convenience stores. (1 ≤ N ≤ 100)

Each of the next N lines contains Xi and Yi, the price information for the i-th store. This means Xi won for Yi grams. (1 ≤ Xi ≤ 100, 1 ≤ Yi ≤ 1,000)

Output

Print the minimum cost of buying 1,000 grams of triangular gimbap. An absolute or relative error up to 0.01 is accepted.

Examples3

Example 1
Input
```
5 100
3
4 100
3 100
7 100
```
Expected output
```
30.00
```

Example 2

Input

Expected output

69.55

Example 3
Input
```
100 5
3
99 8
65 14
78 10
```
Expected output
```
4642.86
```