Лимит времени 1000/1000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Петя долго-долго сидел у окна и наблюдал, как n ворон, каждая в свое гнездо,
приносят монеты.
Петя заметил, что i-ая ворона принесла в свое гнездо ai монет. Опытным глазом
Петя подметил,
что если в i-ом гнезде окажется bi монет, то гнездо со всем своим содержимым
упадет на землю, и
все монеты достанутся Пете.
У Пети есть m монет. Петя очень метко кидает монеты в гнезда. Помогите Пете
узнать, какое
максимальное число монет он может получить.
Формат входного файла
В первой строке входного файла находятся два целых числа n и m (1 ≤ n ≤ 1000, 0
≤ m ≤ 1000) —
число ворон и монет у Пети соответственно. Во второй строке находятся n чисел ai
(0 ≤ ai ≤ 1000).
В третьей строке находятся n чисел bi (ai < bi ≤ 1000).
Формат выходного файла
В выходной файл выведите одно число — максимальное число монет, которые Петя
может
получить.
Примеры
input
2 3
1 2
4 6
output
6
input
3 3
1 2 3
4 8 16
ouput
4
Для отправки решений необходимо выполнить вход.
|