P15491 [IOI 2004] Farmer

一位农民拥有若干田地，每块田地都被柏树环绕。此外，农民还有一些条状土地，每条土地上都种植着一排柏树。在田地和条状土地中，每两棵相邻的柏树之间都长有一棵橄榄树。农民的所有柏树要么环绕着田地，要么位于条状土地中；而所有橄榄树都生长在田地或条状土地中两棵相邻的柏树之间。 一天，农夫病重，感觉自己将不久于人世。在去世前几天，他把长子叫到身边，告诉他：“我让你任意选择 $Q$ 棵柏树，以及所有在你所选柏树中每两棵相邻柏树之间的橄榄树。”从每块田地和每条条状土地中，儿子都可以选择任意组合的柏树。由于长子喜爱橄榄，他希望选出那 $Q$ 棵柏树，以便继承尽可能多的橄榄树。  在图中，假设儿子被给予 $Q=17$ 棵柏树。为了最大化他的橄榄树继承数量，他应选择 Field 1 和 Field 2 中的所有柏树，从而继承 $17$ 棵橄榄树。 请编写一个程序，根据给定的田地和条状土地的信息，以及儿子可以选择的柏树数量，确定儿子可能继承的橄榄树的最大数量。

第一行依次包含整数 $Q$：儿子需选择的柏树数量；整数 $M$：田地数量；以及整数 $K$：条状土地数量。 第二行包含 $M$ 个整数 $N_1,N_2,\dots,N_M$：各田地的柏树数量。 第三行包含 $K$ 个整数 $R_1,R_2,\dots,R_K$：各条状土地的柏树数量。

包含一行，即一个整数：表示儿子可能继承的橄榄树的最大数量。

在所有输入中，$0\le Q\le 150000$，$0\le M\le 2000$，$0\le K\le 2000$，$3\le N_1\le 150,3\le N_2\le 150,\dots,3\le N_M\le 150$，$2\le R_1\le 150,2\le R_2\le 150,\dots,2\le R_K\le 150$。田地与条状土地中的柏树总数至少为 $Q$。 此外，在 $50\%$ 的输入中，$Q\le 1500$。