#3897. 硬币问题(C++四级)

硬币问题(C++四级)

题目描述

有N(不大于100)种硬币,编号为1至N,已知每种硬币的重量(不超过100的正整数)和面额(不超过100的正整数),每种硬币数量不限。选取总重量不超过C(不大于1000的正整数)的硬币,最多能获得多少总面额?

时间限制:1000

内存限制:65536

输入

第一行输入N 第二行输入C 第三行输入各硬币重量,用空格隔开 第四行输入各硬币价值,用空格隔开

输出

最大总面额

样例输入

3
5
1 2 5
1 3 6

样例输出

6

Limitation

1s, 1024KiB for each test case.