1033 Fill/Not Greedy Algorithm (25)

题目

With highways accessible, traveling by car from Hangzhou to any other city becomes straightforward. However, due to the limited fuel tank capacity of a car, drivers must periodically stop for refueling at gas stations along the route. Nevertheless, different gas stations may offer varying prices; your task is to meticulously plan the most cost-effective route.

输入规格：
每个输入文件包含一个测试用例。对于每个用例来说，在第一行中给出四个正数：C_{\text{max}}（不大于100），油箱的最大容量；D（不大于3万），杭州至目的地城市之间的距离；D_{\text{avg}}（不大于20），每单位汽油可行驶的距离；以及N（不大于5百），加油站的总数。然后是接下来的N行内容，在每一行中给出两个非负数：P_i（ ith 加油站的单位油价），以及该加油站与杭州的距离D_i（不大于