e386: Bill的跑車沒油了
Tags :
Accepted rate : 11人/29人 ( 38% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-09-17 02:44

Content

Bill 的跑車要從從城市 A 運送包裹到城市 B。在沿途有很多價格不同的加油站。第一個加油站的位置在路程的開始處,也就是城市A的位置。Bill 每一台跑車的油箱容積可能不同,在沿途需要在油箱耗盡前及時給油箱加油,而一單位的油可以讓 Bill 的酷炫跑車跑一單位的路。同時我們假設,每個加油站有足夠的油。

雖然 Bill 開跑車,但是他需要省多一點油錢才能買更多的跑車。請你幫忙計算到達 城市 B 最少要花多少錢。 

 

Input

第一行為一個正整數 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

Output

輸出最低花費

Sample Input #1
40
3
2 10
1 15
2 5
Sample Output #1
40
測資資訊:
記憶體限制: 300 MB
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <10M
公開 測資點#7 (10%): 1.0s , <10M
公開 測資點#8 (10%): 1.0s , <50M
公開 測資點#9 (10%): 1.0s , <50M
Hint :
Tags:
出處:
[管理者:
bl33234679 (StillFantasy)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」