Problem : 254 - Farmer

Problem Statistics

Solved Member: 17　　Submission: 80　　User Tried: 17

Statement:

某一農夫有一些塊狀的農地，每一塊地的周圍種滿了白扁柏樹。該農夫另外也擁有一些長條狀的農地，這些長條狀的農地上則只種了一排白扁柏樹。不管是在塊狀農地或是長條狀農地上，每兩棵相鄰的白扁柏樹之間都種了一棵橄欖樹。這位農夫所擁有的白扁柏樹全都種在他的塊狀農地周圍或是在長條狀農地上，而他所擁有的橄欖樹則也全都種在白扁柏樹之間。

有一天，農夫生了重病，且意識到他可能會撐不過這次的重病。在他過世前幾天，他把大兒子叫到身邊並告訴他：「你可以任選Q 棵白扁柏樹，而你所選的連續兩棵白扁柏樹之間的橄欖樹也都歸你」。大兒子可從任何的塊狀農地及長條狀農地中任選白扁柏樹。因為大兒子非常喜歡橄欖樹，因此他希望他所挑中的白扁柏樹能夠讓他繼承越多橄欖樹越好。

在圖例一中，假設大兒子必須選擇 Q=17 棵白扁柏樹，如要繼承最多橄欖樹的話，他就應應該選擇第一塊農地及第二塊農地上的所有白扁柏樹，從而繼承17棵橄欖樹。

請寫一個程式，當給定所有塊狀農地、長條狀農地資訊及所需選擇的白扁柏樹個數時，找出大兒子所能繼承的最大橄欖樹數量。

Input:Output:

第一行包含有整數 Q，代表大兒子所需選擇的白扁柏樹數量；整數 M，代表塊狀農地數；及整數 K，代表長條狀農地數。

第二行包含 M 個整數，N₁, N₂,… N_M，其中 N_I 代表第 I 個塊狀農地上的白扁柏樹數量。

第三行包含 K 個整數，R₁, R₂,… R_K，其中 R_J 代表第 J 個長條狀農地上的白扁柏樹數量。

在所有的輸入中， 0 ≤ Q ≤ 150000, 0 ≤ M ≤ 2000, 0 ≤ K ≤ 2000, 3 ≤ N₁ ≤ 150, 3 ≤ N₂ ≤ 150, … 3 ≤ N_M ≤ 150, 2 ≤ R₁ ≤ 150, 2 ≤ R₂ ≤ 150, … 2 ≤ R_K ≤ 150。在所有塊狀及長條狀農地上的總白扁柏樹數量至少會是 Q。除此之外，在50%的輸入檔中，Q ≤ 1500。

輸出應只有一整數，代表大兒子所能繼承的最大橄欖樹數量。

Sample Input:Sample Output:

17 3 3
13 4 8
4 8 6

Source:

IOI 2004

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	16384kb
1	1000ms	16384kb	5
2	1000ms	16384kb	5
3	1000ms	16384kb	5
4	1000ms	16384kb	5
5	1000ms	16384kb	5
6	1000ms	16384kb	5
7	1000ms	16384kb	5
8	1000ms	16384kb	5
9	1000ms	16384kb	5
10	1000ms	16384kb	5
11	1000ms	16384kb	5
12	1000ms	16384kb	5
13	1000ms	16384kb	5
14	1000ms	16384kb	5
15	1000ms	16384kb	5
16	1000ms	16384kb	5
17	1000ms	16384kb	5
18	1000ms	16384kb	5
19	1000ms	16384kb	5
20	1000ms	16384kb	5