EduBrick

D. Предметов сколько угодно

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

Тот же рюкзак вместимости 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
вывод
30
ввод
1 10
3
4
вывод
12
Войдите, чтобы отправлять решения.