UOJ Logo X Online Judge

XOJ

#79. 超大背包

统计
Time Limit: 10 s Memory Limit: 256 MB

题目描述

超大背包问题:
有重量和价值分别为wi和vi的n个物品,从这些物品中挑选总重量不超过W的物品,
求所有挑选方案中价值总和最大值

输入格式

输出格式

样例数据

input

4
2 1 3 2
3 2 4 2
5

output

7

说明


数据规模与约定

  限制条件:
1 <= n <= 40
1 <= wi, vi <= 10^15
1 <= W <= 10^15