Hotel

A hotel wants to increase its number of customers by advertising in several cities.

For each city, you are given the cost of one advertising campaign there and the number of new customers gained from one such campaign. A city campaign may be purchased any nonnegative integer number of times. Partial purchases are not allowed, and every city has an unlimited number of potential customers.

Find the minimum amount of money that must be spent to increase the hotel's customers by at least C.

The first line contains two integers C and N. C is a positive integer not greater than 1,000, and N is a positive integer not greater than 20.

Each of the next N lines contains two positive integers: the advertising cost in one city and the number of customers gained for that cost. Each value is not greater than 100.

Print the minimum cost required to gain at least C customers.