KNPSACK - Knapsack

Harry is working on a project with Hermione, in which they need some amount of a specific magical powder. As Hermione is studious type, she instructs Harry to arrange X milligrams of powder while she does some other necessary work.

The powder is available in the market in packed form. Packets of different weights are available. There are M types of packets available in the market each having some price, further each type of packet is available in infinite numbers. Your task is to find what is the minimum amount Harry needs to spend so that he can buy at least X milligrams.

Assume that the max value of answer can be 200.00 only.

Input

In the first line, you are given two integers representing X and M. Next M lines describe the packet details, where each line has two integers Wi (Weight of packet i) and Pi (Price of Packet i). Wi will be a integer where Pi will be decimal number with 2 decimal places.

Output

You need to print the minimum money spent so that Harry can arrange at least X milligrams of powder. Answer must contain exactly two decimal places (i.e. 5 should be printed as 5.00 and 5.6 should be printed as 5.60).

Constraints

1 <= X <= 10^7

1 <= M <= 100

1 <= Wi <= 10^6

0.01 <= Pi <= 100.00

Sample

Input #1:
3 2
1 1.10
2 0.83

Output #1:
1.66
Input #2:
3 2
2 0.95
1 0.50

Output #2:
1.45

Added by:Aditya Dixit
Date:2015-02-20
Time limit:0.300s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: MAWK BC NCSHARP COFFEE DART FORTH GOSU JULIA KTLN OCT PROLOG PYPY3 R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2020-08-03 21:48:51
"Assume that the max value of answer can be 200.00 only." DP[i] = max weight at total cost of i.
2020-05-19 22:44:52
how to think of dp on this
2018-08-09 23:34:34
Nice dp!
2016-09-26 19:09:11
You have an error in the problem statement. Pi should be of type float, not int.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.