內容
Bill 的跑車要從從城市 A 運送包裹到城市 B。在沿途有很多價格不同的加油站。第一個加油站的位置在路程的開始處，也就是城市Ａ的位置。Bill 每一台跑車的油箱容積可能不同，在沿途需要在油箱耗盡前及時給油箱加油，而一單位的油可以讓 Bill 的酷炫跑車跑一單位的路。同時我們假設，每個加油站有足夠的油。
雖然 Bill 開跑車，但是他需要省多一點油錢才能買更多的跑車。請你幫忙計算到達 城市 B 最少要花多少錢。
輸入說明
第一行為一個正整數 p 表示油箱的容量.
第二行為一個正整數 n 表示沿途加油站的數目。
接下來的 n 行每行有兩個用單個正整數分隔的整數 ci di, 其中 ci 表示第 i 加油站的價格. di 表示 i 和第 (i + 1) 個加油站的距離 (注意：dn 就是最後一個油站到結束點的距離).
30%的測資 1 <= n <= 100
60%的測資 1 <= n <= 10000
100%的測資 1 <= n <= 1000000
100%的測資 1 <= ci <= 1000, 1 <= di <= 1000000, 1 <= p <= 1000000
輸出說明
輸出最低花費
範例輸入
#1
40 3 2 10 1 15 2 5
範例輸出
#1
40
測資資訊：
記憶體限制：
300
MB
提示 ：
標籤:
出處:
[管理者：
bl33234679
(StillFantasy)
]