Задача №112518. Фермер
У фермера есть несолько полей, каждое из которых окружено кипарисами. Также у него есть несколько участков земли, на каждом из которых растёт ряд кипарисов. И на полях, и на участках между любыми двумя последовательными кипарисами растёт ровно одна олива. Каждый кипарис фермера либо растёт на границе какого-то поля, либо образуют ряд кипарисов, а каждая олива находится между какими-то двумя последовательными кипарисами.
Однажды фермер сильно заболел и почувствовал, что он скоро умрёт. За несколько дней до того, как он скончался, он позвал своего старшего сына и сказал ему: «Я оставляю тебе любые Q кипарисов, которые ты выберешь, и все те оливы, для которых ты выбрал оба соседних с ней кипариса.» На каждом поле и на каждом участке сын может выбрать любой набор кипарисов. Так как старший сын любит оливы, он хочет выбрать Q кипарисов так, чтобы унаследовать как можно больше олив.
Напишите программу, которая по данной информации о полях и участках, а также по количеству кипарисов, которые может выбрать сын, посчитает максимальное возможное количество олив, которые он может унаследовать.
Первая строка ввода содержит три целых числа Q , M и K "— количество кипарисов, которые сын должен выбрать, количество полей и количество участков, соответственно ( 0 ≤ Q ≤ 150 000 , 0 ≤ M ≤ 2000 , 0 ≤ K ≤ 2000 ). Вторая строка содержит M целых чисел N i "— количество кипарисов на соответствующих полях ( 1 ≤ i ≤ M , 3 ≤ N i ≤ 150 ). Третья строка содержит K целых чисел R i "— количество кипарисов на соответствующих учасках ( 1 ≤ i ≤ K , 3 ≤ R i ≤ 150 ). Суммарное количество кипарисов на всех полях и участках хотя бы Q . Решения, работающие только для Q ≤ 1500 , будут оцениваться из 50 баллов.
Выходной файл должен содержать единственную строку, в которой находится единственное целое число - максимальное возможное количество олив, которые может унаследовать сын.
17 3 3 13 4 8 4 8 6
17