You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

烤乐滋想让你解决这个问题：

有 $n$ 个物品，每个物品重量为 $w_i$ 元，价格为 $v_i$ 元，你需要求出你有 $m$ 大小的背包最大能拿走多少总价值的物品。

每个物品只能买一次。

输入格式

第一行两个正整数 $n,m$，

第二行 $n$ 个正整数 $w_i$，

第三行 $n$ 个正整数 $v_i$。

输出格式

一行一个正整数表示你的答案。

输入输出样例 #1

输入 #1

3 3
1 2 2
1 2 3

输出 #1

3

输入输出样例 #2

输入 #2

5 7
3 2 1 2 1
2 2 1 3 1

输出 #2

7

输入输出样例 #3

输入 #3

16 24
1 1 1 1 2 3 1 2 3 3 2 2 3 3 2 3
5 2 5 3 4 10 1 9 6 1 8 5 7 7 6 8

输出 #3

75

说明/提示

【样例解释 #1】

这里我们可以选择第 $1$ 件和第 $3$ 件商品，总的价值是 $4$。

【样例解释 #2】

选择第 $1,3,4,5$ 个商品，也可以选择第 $2,3,4,5$ 个物品。

【数据范围】

对于 $50\%$ 的数据，满足 $1 \le n \le 2000$，$1 \le m \le 6000$，

对于另外 $10\%$ 的数据，满足 $n=50000$ 且 $w_i$ 的取值最多为一个，

对于另外 $10\%$ 的数据，满足 $n=80000$ 且 $w_i$ 的取值最多为一个，

对于另外 $10\%$ 的数据，满足 $w_i$ 的取值最多为两个，

对于 $100\%$ 的数据，满足 $1 \le n \le 10^5$，$1 \le m \le 3 \times 10^5$，$1 \le v_i \le 10^6$，$1 \le w_i \le 3$。