Farmer
The farmer owns several fields, each bordered by cypress trees, as well as strips of land, each lined with a row of cypress trees. Between every pair of consecutive cypress trees, whether on the field borders or on the strips, an olive tree grows. All the farmer's cypress trees are positioned either on the field borders or on the strips, and all the olive trees are located between two neighboring cypress trees on these borders or strips.
One day, the farmer fell gravely ill and sensed that his end was near. A few days before his passing, he summoned his eldest son and said: "I bequeath to you any Q cypress trees of your choice, along with all the olive trees that grow between any two consecutive cypress trees you select". From each field and each strip, the son can choose any combination of trees. Since the eldest son has a fondness for olives, he aims to select such Q cypress trees that will allow him to inherit the maximum number of olive trees.
Strip 1 contains 4 cypress trees
Strip 2 contains 8 cypress trees
Strip 3 contains 6 cypress trees
Fig. 1. Example of cypress tree placement
(olive trees not shown)
Consider an example where the son receives Q=17 cypress trees for the fields and strips shown in Fig. 1. To maximize the number of inherited olive trees, he should choose all the cypress trees in field 1 and field 2, thus obtaining 17 olive trees.
Your task is to write a program that, given the details about the fields, strips, and the number of cypress trees chosen by the son, calculates the maximum possible number of olive trees the son can inherit.
Input
The first line of the input file contains three integers: Q (0 ≤ Q ≤ 150000) – the number of cypress trees the son must choose, M (0 ≤ M ≤ 2000) – the number of fields, and K (0 ≤ K ≤ 2000) – the number of strips. The second line contains M integers N_1, N_2, ..., N_M (3 ≤ N_{1 }≤ 150, 3 ≤ N_{2 }≤ 150, ..., 3 ≤ N_M_{ }≤ 150) – the number of cypress trees in the fields. The third line contains K integers R_1, R_2, ..., R_K (2 ≤ R_{1 }≤ 150, 2 ≤ R_{2 }≤ 150, ..., 2 ≤ R_K_{ }≤ 150) – the number of cypress trees in the strips.
Output
The output should be a single integer on one line – the maximum possible number of olive trees the son can inherit.