UOJ Logo 小司码 Online Judge

XSMOJ

第453题   01背包

统计 下一题 上一题

题目描述

有 n 件物品,每件物品有一个重量和一个价值,分别记为 W1 ,W2 ,…,Wn 和 C1 ,C2 ,…,Cn 。现在有一个背包,其容量为 WK,要从 n 件物品种任取若干件,要求: (1) 重量之和小于或等于 WK。 (2) 价值之和最大。

输入格式

第 1 行 2 个整数,表示 n和WK,1≤n≤20,1≤WK≤10^6 。 第 2 行 n 个整数,表示每一个物品的重量,1≤Wi ≤10^4 。 第 3 行 n 个整数,表示每一个物品的价值,1≤Ci ≤10^8 。

输出格式

一行一个数,表示符合背包容量的最大价值。

样例数据

input


8 200
79 58 86 11 28 62 15 68
83 14 54 79 72 52 48 62

output

334

数据规模与约定

时间限制:$1 \text{s}$

空间限制:$256 \text{MB}$