EduBrick

D. Рюкзак максимальной стоимости

2000 мс · 256 МБ · всё или ничего

Дано nn предметов: предмет номер ii весит mim_i и стоит cic_i. Рюкзак выдерживает вес не более ww.

Определите наибольшую стоимость, которую можно унести.

Формат ввода

Первая строка содержит числа nn (1≤n≤1001 \le n \le 100) и ww (1≤w≤1041 \le w \le 10^4).

Вторая строка содержит nn натуральных чисел mim_i, не превосходящих 100.

Третья строка содержит nn натуральных чисел cic_i, не превосходящих 100.

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

Одно число — наибольшая суммарная стоимость.

Примеры

ввод
4 6
2 4 1 2
7 2 5 1
вывод
13
Войдите, чтобы отправлять решения.