[POI1997]汽油花费

Grade 0 Open Time Tuesday, 22 January 2013, 10:35 am
Discount 0.8 Time Discount Tuesday, 22 January 2013, 10:35 am
Allow late Yes Close Time Tuesday, 22 January 2013, 10:35 am
Input file pal.in Output file pal.out

一些旅行车从城市A到城市B运送包裹。在沿途由很多价格不同的加油站。第一个加油站的位置在路程的开始。旅行车的油箱容积可能不同,车在沿途需要及时给油箱加油,我们假设,每个油站有足够的油。

输入

在文件的第一行为一个整数p表示油箱的容量, 1 < p <= 1000000. 在第二行有一个整数n表是沿途加油站的数目。1 < n <= 1000000.接下来的n行每行有两个用单个正整数分隔的整数ci, di, 其中ci表示第I油站的价格. di 表示I和第(i+1)个油站的距离- (dn 就是最后一个油站到结束点的距离). 1 <= ci <= 1000, 1 <= di <= 1000000.

AB的路线长度(所有di之和) 不超过1000000.

输出

一个整数,为路线AB中加油的最少花费

样例输入

40
3
2 10
1 15
2 5

样例输出

40