[POI1997]汽油花费

成绩 0 开启时间 2013年01月22日 星期二 10:35
折扣 0.8 折扣时间 2013年01月22日 星期二 10:35
允许迟交 是 关闭时间 2013年01月22日 星期二 10:35
输入文件 pal.in 输出文件 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