0 人解决，2 人已尝试。
0 份提交通过，共有 4 份提交。
9.9 EMB 奖励。
单点时限: 5.0 sec
内存限制: 256 MB
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.
Write a program that:
* reads the following data: @ the capacity of the fuel tank in a car, @ the number of petrol stations on the route from A to B, @ the price of petrol at each station and the distances between consecutive stations, * computes the minimal cost of refuelling on the route AB for the car with the given capacity of the fuel tank, * writes the result.
In the first line 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 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.
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.
40 3 2 10 1 15 2 5
40
0 人解决，2 人已尝试。
0 份提交通过，共有 4 份提交。
9.9 EMB 奖励。