Задача G. Внеклассное чтение ≡

Условие

Чем заняться летом? Да чем угодно! Можно ходить в лес за грибами и ягодами, купаться в речке, загорать под ярким солнцем, общаться с друзьями и ... готовиться к новому учебному году. Тимофею за d дней каникул нужно прочитать k книг. Для каждой i-й книги известны два параметра: x_i - количество дней, необходимых для её чтения, и y_i - условные единицы удовольствия, которое получит Тимофей после прочтения этой книги. Есть, правда, еще один вариант - всю книгу целиком можно не читать, а потратить 1 день и познакомиться с её содержанием в хрестоматии "Полное собрание всех книг на лето в кратком пересказе", естественно, не получив никакого удовольствия.

Помогите Тимофею определить наибольшее удовольствие от чтения за время каникул. Тимофей - мальчик ответственный, поэтому каждая книга из списка должна быть прочитана либо полностью, либо в кратком пересказе.

Формат входных данных

Первая строка входного файла содержит два натуральных числа, записанных через пробел: d и k. Во второй строке через пробел записаны k натуральных чисел x_i. В третьей строке через пробел записаны k натуральных чисел y_i.

Формат выходных данных

Выведите одно неотрицательное целое число - ответ на задачу.

Ограничения

1 ≤ k ≤ 100

k ≤ d ≤ 1000

2 ≤ x_i, y_i ≤ 100

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Пояснение к примерам

В первом примере первую и четвертую книги Тимофей прочтет в хрестоматии, потратив на это два дня и не получив удовольствия. Вторую, третью и пятую книги он прочтет целиком, потратив на это 2 + 4 + 2 = 8 дней и получив 9 + 4 + 5 = 18 единиц удовольствия. Всего на чтение потрачено 10 дней.

Во втором примере у Тимофея слишком мало времени - он не успеет прочитать полностью ни одной книги. Потратив два дня на хрестоматию, Тимофей не получит никакого удовольствия.

Примеры тестов

10 5
3 2 4 3 2
5 4 9 7 5

18

3 2
5 7
8 10

0