Фермер#2127

Фермер

1 секунда

64 мегабайти

Дуже легка

У фермера є кілька полів, кожне з яких обмежене кипарисовими деревами, а також смуги землі, кожна з яких обсаджена рядом кипарисів. Між кожною парою послідовних кипарисів, як на межах полів, так і на смугах, росте оливкове дерево. Усі кипариси фермера розташовані або на межах полів, або на смугах, а всі оливкові дерева знаходяться між двома сусідніми кипарисами на цих межах або смугах.

Одного дня фермер тяжко захворів і відчув, що його кінець близький. За кілька днів до своєї смерті, він покликав свого старшого сина і сказав: "Я заповідаю тобі будь-які Q дерев кипариса на твій вибір, а також всі оливкові дерева, що ростуть між будь-якими двома послідовними вибраними тобою кипарисами." З кожного поля і кожної смуги син може обирати будь-яку комбінацію дерев. Оскільки старший син дуже любить оливки, він прагне вибрати такі $Q$ кипарисів, щоб отримати якнайбільше оливкових дерев у спадок.

Смуга $1$ містить $4$ кипариси

Смуга $2$ містить $8$ кипарисів

Смуга $3$ містить $6$ кипарисів

Рис. $1$ . Приклад розміщення кипарисів

(оливки не показані)

Розглянемо приклад, коли син отримує $Q = 17$ Q=17 кипарисів із зображених на Рис. 1 полів і смуг. Щоб отримати максимальну кількість оливкових дерев, йому слід вибрати всі кипариси на полі $1$ та полі $2$ , і таким чином він отримає $17$ оливкових дерев.

Ваше завдання — написати програму, яка, знаючи інформацію про поля, смуги і кількість кипарисів, обраних сином, обчислює максимальну можливу кількість оливкових дерев, які може отримати син.

Вхідні дані

У першому рядку вхідного файлу знаходяться три цілі числа: $Q$ ( $0 \leq Q \leq 150000$ 0 \leq Q \leq 150\,000) — кількість кипарисів, які повинен вибрати син, $M$ ( $0 \leq M \leq 2000$ 0 \leq M \leq 2\,000) — кількість полів та $K$ ( $0 \leq K \leq 2000$ 0 \leq K \leq 2\,000) — кількість смуг.

У другому рядку знаходяться $M$ цілих чисел $N_{1}, N_{2}, \dots, N_{M}$ N_1, N_2, \ldots, N_M ( $3 \leq N_{1} \leq 150$ 3 \leq N_1 \leq 150, $3 \leq N_{2} \leq 150$ 3 \leq N_2 \leq 150, $\dots$ , $3 \leq N_{M} \leq 150$ 3 \leq N_M \leq 150) — кількість кипарисів на кожному полі.

У третьому рядку міститься $K$ цілих чисел $R_{1}, R_{2}, \dots, R_{K}$ R_1, R_2, \ldots, R_K ( $2 \leq R_{1} \leq 150$ 2 \leq R_1 \leq 150, $2 \leq R_{2} \leq 150$ 2 \leq R_2 \leq 150, $\dots$ , $2 \leq R_{K} \leq 150$ 2 \leq R_K \leq 150) — кількість кипарисів на кожній смузі.

Вихідні дані

Виведіть одне число в одному рядку — максимальну можливу кількість оливкових дерев, які може отримати син.

Приклади

Приклад 1