222 - Budget Travel

本題請你計算開車從一地開往另一地最少所需的費用，旅程沿途會有一些加油站，每個加油站的油價不儘相同。

為了簡化問題，我們定義駕駛者的行為如下：

• 當油箱的油超過一半的時候，駕駛者不會停下來加油，除非剩下的油無法讓他到達下一個加油站(或終點)。
• 當駕駛者停下來到加油站加油的時候，他一定會把油加滿。
• 當駕駛者停下來來加油的時候，他會額外多花2塊錢來買些零食或其他什麼的。
• 駕駛者不需要為油箱保留一個「安全的額度」，即到達下一個加油站前都不需要多餘的油。
• 駕駛者一開始會把油箱加滿。
• 每次加油的油錢都會做四捨五入進位到幾分錢(100分錢等於1塊錢)。

請你寫一個程式計算駕駛者一路上最少需要花多少錢在油料與零食上。

Input

輸入會有多組測試資料，每組資料格式如下：

第一列：會有一個實數表示終點離起點的距離。

第二列：有三個實數與一個整數：

• 第一個實數表示油箱的容量。
• 第二個實數表示車子每英哩的油耗。
• 第三個實數表示車子於起點加油的油價。
• 以一個整數表示沿途有多少加油站。

接下來每一列會有一個加油站的資訊，每列有兩個實數：

• 第一個實數表示加油站與起點的距離。
• 第二個實數表示該加油站每加侖的油價(單位為一分錢=0.01元)。

每個數值皆為正值。加油站出現的順序以距離起點的距離由小到大排列，且不會大於終點的距離。不會存在無法到達終點的情況。當出現負值表示測試資料結束。

Output

請參考範列資料輸出每組資料編號及最少所需的費用，費用請包含於起點加油所需的花費。

Sample Input

475.6
11.9 27.4 14.98 6
102.0 99.9
220.0 132.9
256.3 147.9
275.0 102.9
277.6 112.9
381.8 100.9
516.3
15.7 22.1 20.87 3
125.4 125.9
297.9 112.9
345.2 99.9
-1

Sample Output

Data Set #1
minimum cost = $27.31
Data Set #2
minimum cost = $38.09

原文出處