TopCoder

腦子裝咖哩

想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

85.5% (47/55)

Submission's AC Ratio

31.1% (113/363)

Description

快樂暑假，要作什麼呢？當然是釣魚囉！

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

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

Input Format

輸入檔可能包含多筆測試資料。每筆測試資料的第一列包含兩個正整數 $T, n$ ，分別代表限制的時間以及魚池的總數。
（ $1 \leq T, n \leq 10^{5}$ ，但是 $n T \leq 10^{7}$ ）

接下來依序有 $n$ 個整數依據離入口遠近表示出每個魚池第一次的魚穫量 $F_{i}$ 。（ $0 \leq F_{i} \leq 10^{5}$ ）
然後的 $n$ 個整數依序是對應魚池的每次撈魚減少量 $D_{i}$ 。（ $0 \leq 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

Sample Output 1

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 (VSS, 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

1399 . 超級撈魚活動

TopCoder

User's AC Ratio

Submission's AC Ratio

Tags

Description

Input Format

Output Format

Sample Input 1

Sample Output 1

Hints

Problem Source

Subtasks

Testdata and Limits

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

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

1399 . 超級撈魚活動

TopCoder

User's AC Ratio

Submission's AC Ratio

Tags Show solution-related tags

Description

Input Format

Output Format

Sample Input 1

Sample Output 1

Hints

Problem Source

Subtasks

Testdata and Limits

Tags

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