FARMER  Farmer
A farmer has a set of fields, each of which is surrounded by cypress trees. Also, the farmer
has a set of strips of land, each of which has a row of cypress trees. In both fields and strips,
between every two consecutive cypress trees is a single olive tree. All of the farmer’s
cypress trees either surround a field or are in a strip and all of the farmer’s olive trees are
between two consecutive cypress trees in a field or in a strip.
One day the farmer became very ill and he felt that he was going to die. A few days before
he passed away he called his eldest son and told him, “I give you any Q cypress trees of
your choice and all the olive trees which are between any two consecutive cypress trees you
have chosen.” >From each field and from each strip the son can pick any combination of
cypress trees. Since the eldest son loves olives he wants to pick the Q cypress trees which
will allow him to inherit as many olive trees as possible.
In Figure 1, assume that the son is given Q=17 cypress trees. To maximize his olive
inheritance he should choose all the cypress trees in Field 1 and Field 2, inheriting 17 olive
trees.
You are to write a program which, given the information about the fields and the strips and
the number of cypress trees the son can pick, determines the largest possible number of
olive trees the son may inherit.
Input
t  the number of test cases [t <= 20], then t test cses follows.
The first line of each test case contains first the integer Q: the number of cypress trees the son is to select;
then the integer M, the number of fields; and then the
integer K, the number of strips. The second line contains M integers N1, N2,… NM, : the
numbers of cypress trees in fields. The third line contains K integers R1, R2,… RK: the
numbers of cypress trees in strips.
In all test cases, 0 <= Q <= 150000, 0 <= M <= 2000, 0 <= K <= 2000, 3 <= N1 <= 150, 3 <= N2 <= 150,… 3 <= NM <=150,
2 <= R1 <= 150, 2 <= R2 <= 150,… 2 <= RK <= 150. The total number of cypress trees in the fields and
strips is at least Q. Additionally, in 50% of the test cases, Q <= 1500.
Output
For each test case output ont integer: largest possible number of olive trees the son may inherit.
Example
Input: 1 17 3 3 13 4 8 4 8 6
Output: 17
hide comments
sonuverma:
20190121 17:12:43
Nice Problem, You can use "https://www.geeksforgeeks.org/subsetsumproblemdp25/" this link for reference. 

Shubham Jadhav:
20170508 23:23:18
Nice Problem :) Don't think too much 

Bee:
20150618 16:07:43
bài này không Toolkit được ! 

Edward Kenway:
20150417 17:17:04
bạn cho mình hỏi theo mình 2 test đó phải ra 30 vs 35 chứ sao lại 31 vs 36


Edward Kenway:
20150417 17:16:25
bạn cho mình hỏi tại sao 2 test đó theo mình ra 30 vs 35 mới phải chứ tại sao lại ra 31 36


Deepak Gupta:
20141208 23:02:35
Useful Test Cases :

Added by:  Roman Sol 
Date:  20050522 
Time limit:  50s 
Source limit:  30000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  IOI 2004 