Niebieskie ksi.eczki
IV Olimpiada Informatyczna 1996/1997

Task: PAL
Author: Tomasz Śmigielski
Petrol

II stage contest  
Source filePAL.??? (e.g. PAS,C, CPP)
Executable filePAL.EXE
Input filePAL.IN
Output filePAL.OUT

The haulage contractor carries packages from town A to town B. Packages are transported by cars. Petrol stations along the route offer petrol at various prices. The first station is situated at the beginning of the route. All cars, which the contractor has at his disposal, use one standard unit of petrol per mile but capacities of their fuel tanks can differ. Cost of petrol needed to cover the distance from A to B depends on the capacity of the tank in a car and the chosen plan of refuelling. We assume that each petrol station has enough petrol to fill up a fuel tank of every car. Petrol stations are placed in such a way that each car can travel from A to B.

Task

Write a program that:

Input

In the first line of the text file PAL.IN there is written the capacity of the fuel tank of the car. This capacity is an integer p, 1 < p <= 1000000.

In the second line of the same file there is an integer n, 1 < n <= 1000000 - the number of petrol stations on the route from A to B.

In each of the following n lines there is a pair of positive integers ci, di, separated by a single space. The number ci is the price of a standard petrol unit at the i-th station (the numbers of petrol stations increase when we go away from A). The number di is the distance (in miles) between the i-th and the (i+1)-st station (dn is the distance from the last station to the end of the route AB). The numbers meet the following conditions: 1 <= ci <= 1000, 1 <= di <= 1000000.

The length of the route AB (the sum of di) is not greater than 1000000.

Output

In the text file PAL.IN there should be written one integer - the minimal cost of refuelling on the route AB for a car with the fuel tank of the given capacity.

Example

For the file PAL.IN
40
3
2 10
1 15
2 5
the correct solution is the file
40