Фермер
Фермер владеет несколькими полями, на границе каждого из которых растут кипарисовые деревья. У фермера также есть полоски земли, на каждой из которых растет ряд кипарисовых деревьев. На границах полей и на полосках между каждой парой подряд стоящих кипарисовых деревьев растет одно оливковое дерево. Все кипарисовые деревья фермера растут либо по границе поля, либо на полоске, и все оливковые деревья фермера находятся между двумя соседними кипарисовыми деревьями на границе поля или на полоске.
Однажды фермер сильно заболел и почувствовал, что скоро умрет. За несколько дней до смерти он позвал своего старшего сына и сказал ему: "Я завещаю тебе любые Q кипарисовых деревьев на твой выбор, а также все оливковые деревья, которые растут между любыми двумя подряд стоящими кипарисовыми деревьями, выбранными тобой". Из каждого поля и из каждой полоски сын может выбрать любую комбинацию деревьев. Так как старший сын любит оливки, он хочет выбрать такие Q кипарисовых деревьев, которые позволят ему унаследовать как можно большее количество оливковых деревьев.
Полоска 1 содержит 4 кипарисовых дерева
Полоска 2 содержит 8 кипарисовых деревьев
Полоска 3 содержит 6 кипарисовых деревьев
Рис. 1. Пример размещения кипарисовых деревьев
(оливковые деревья не изображены)
Расмотрим пример, когда сын получает для полей и полосок, изображенных на рис. 1, Q=17 кипарисовых деревьев. Для того, чтобы максимизировать количество унаследованных оливковых деревьев, он должен выбрать все кипарисовые деревья на поле 1 и поле 2, получив, таким образом, 17 оливковых деревьев.
Требуется написать программу, которая по информации о полях, полосках и количестве выбираемых сыном кипарисовых деревьев определяет наибольшее возможное количество оливковых деревьев, которое сын может унаследовать.
Входные данные
Первая строка входного файла содержит три целых числа Q (0 ≤ Q ≤ 150000) – количество кипарисовых деревьев, которое должен выбрать сын, затем M (0 ≤ M ≤ 2000) – количество полей и затем K (0 ≤ K ≤ 2000) – количество полосок. Вторая строка содержит M целых чисел N_1, N_2, ..., N_M (3 ≤ N_{1 }≤ 150, 3 ≤ N_{2 }≤ 150, ..., 3 ≤ N_M≤ 150) – количества кипарисовых деревьев на полях. Третья строка содержит K целых чисел R_1, R_2, ..., R_K (2 ≤R_{1 }≤ 150, 2 ≤ R_{2 }≤ 150, ..., 2 ≤ R_K_{ }≤ 150) – количества кипарисовых деревьев в полосках.
Выходные данные
В единственной строке выходного файла должно находиться одно целое число – наибольшее возможное количество оливковых деревьев, которое может унаследовать сын.