TopCoder

Thumb ya2
赤ずきんチャチャ
もっと心の中を二人見せ合えたなら 答えはつかめるよ

User's AC Ratio

88.9% (8/9)

Submission's AC Ratio

34.0% (16/47)

Description

快樂暑假,要作什麼呢?當然是釣魚囉!

「快樂暑假營隊」最近舉辦了超級撈魚比賽:在一個直線型的道路上,有許多魚池。參賽者們在給定的時間之內,從入口開始,沿途撈魚,撈最多的人就贏了。每一單位的時間都可以撈一次魚,而在每一個魚池第一次撈魚所獲得的魚數量為 Fi,第二次以後在相同魚池所撈的魚穫量都會比前一次少 Di 個(若小於零則代表撈不到魚了)。此外,來往於兩個魚池之間也需要花時間。

請問給定時間限制以及已知各個魚池的魚穫量,能夠在限制時間之內撈到的最多魚數量為何?

Input Format

輸入檔可能包含多筆測試資料。每筆測試資料的第一列包含兩個正整數 T, n,分別代表限制的時間以及魚池的總數。
(1<=T, n<=100,000,但是 n*T<=10,000,000)

接下來依序有n個整數依據離入口遠近表示出每個魚池第一次的魚穫量 Fi。(0<=Fi<=100,000)
然後的n個整數依序是對應魚池的每次撈魚減少量 Di。(0<=Di,Fi)
最後一列有n個整數 Ti,依序代表來往入口與第一魚池所耗費的時間、來往第一與第二魚池所耗費的時間,...以此類推。

Output Format

對於每一筆測試資料,請輸出一列包含一個整數:最多可以撈到多少魚。

Sample Input

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

Sample Output

31
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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2500 65536 262144 1
1 2500 65536 262144 2
2 2500 65536 262144 3
3 2500 65536 262144 4
4 2500 65536 262144 5
5 2500 65536 262144 6
6 2500 65536 262144 7
7 2500 65536 262144 8
8 2500 65536 262144 9
9 2500 65536 262144 10
10 2500 65536 262144 11
11 2500 65536 262144 12
12 2500 65536 262144 13
13 2500 65536 262144 14
14 2500 65536 262144 15
15 2500 65536 262144 16
16 2500 65536 262144 17
17 2500 65536 262144 18
18 2500 65536 262144 19
19 2500 65536 262144 20