Petrol

Memory limit: 32 MB

The haulage contractor carries packages from town to town . 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 to 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 to .

Task

Write a program that:

• reads the following data from the standard input;
  • the capacity of the fuel tank in a car,
  • the number of petrol stations on the route from to ,
  • the price of petrol at each station and the distances between consecutive stations,
• computes the minimal cost of refuelling on the route for the car with the given capacity of the fuel tank,
• writes the result to the standard output.

Input

In the first line of the standard input there is written the capacity of the fuel tank of the car. This capacity is an integer , . In the second line there is an integer , — the number of petrol stations on the route from to .

In each of the following lines there is a pair of positive integers , separated by a single space. The number is the price of a standard petrol unit at the -th station (the numbers of petrol stations increase when we go away from ). The number is the distance (in miles) between the -th and the -st station ( is the distance from the last station to the end of the route ). The numbers meet the following conditions: , .

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

Output

In the standard output there should be written one integer — the minimal cost of refuelling on the route for a car with the fuel tank of the given capacity.

Example

For the input data:

40
3
10 2
15 1
5 2

the correct result is:

40

Task author: Tomasz Smigielski.