1399 . 超級撈魚活動
TopCoder
Tags
Description
快樂暑假，要作什麼呢？當然是釣魚囉！
「快樂暑假營隊」最近舉辦了超級撈魚比賽：在一個直線型的道路上，有許多魚池。參賽者們在給定的時間之內，從入口開始，沿途撈魚，撈最多的人就贏了。每一單位的時間都可以撈一次魚，而在每一個魚池第一次撈魚所獲得的魚數量為 $F_i$，第二次以後在相同魚池所撈的魚穫量都會比前一次少 $D_i$ 個（若小於零則代表撈不到魚了）。此外，來往於兩個魚池之間也需要花時間。
請問給定時間限制以及已知各個魚池的魚穫量，能夠在限制時間之內撈到的最多魚數量為何？
Input Format
輸入檔可能包含多筆測試資料。每筆測試資料的第一列包含兩個正整數 $T, n$，分別代表限制的時間以及魚池的總數。
（$1 \le T, n \le 10 ^ 5$，但是 $nT \le 10 ^ 7$）
接下來依序有 $n$ 個整數依據離入口遠近表示出每個魚池第一次的魚穫量 $F_i$。（$0 \le F_i \le 10 ^ 5$）
然後的 $n$ 個整數依序是對應魚池的每次撈魚減少量 $D_i$。（$0 \le D_i, F_i$)
最後一列有 $n$ 個整數 $T_i$，依序代表來往入口與第一魚池所耗費的時間、來往第一與第二魚池所耗費的時間⋯⋯以此類推。
Output Format
對於每一筆測試資料，請輸出一列包含一個整數：最多可以撈到多少魚。
Sample Input 1
12 2
10 1
2 5
0 2
48 4
10 15 20 17
0 3 4 3
0 1 2 3
48 4
10 15 50 30
0 3 4 3
0 1 2 3
10 1
2 5
0 2
48 4
10 15 20 17
0 3 4 3
0 1 2 3
48 4
10 15 50 30
0 3 4 3
0 1 2 3
Sample Output 1
31
480
724
480
724
Hints
※2008/09/18：輸入敘述修正，感謝peter50216！
Problem Source
原TIOJ1399 / 快樂暑假營第四次練習比賽。Problem Setter：Tmt。
(Adapted From PKU 1042, 算法藝術P.10, BOI 2001)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 5 |
| 2 | 1 | 5 |
| 3 | 2 | 5 |
| 4 | 3 | 5 |
| 5 | 4 | 5 |
| 6 | 5 | 5 |
| 7 | 6 | 5 |
| 8 | 7 | 5 |
| 9 | 8 | 5 |
| 10 | 9 | 5 |
| 11 | 10 | 5 |
| 12 | 11 | 5 |
| 13 | 12 | 5 |
| 14 | 13 | 5 |
| 15 | 14 | 5 |
| 16 | 15 | 5 |
| 17 | 16 | 5 |
| 18 | 17 | 5 |
| 19 | 18 | 5 |
| 20 | 19 | 5 |