#P17743. 背包

背包

题目描述

有 nn 种物品,第 ii 种物品有 cic_i 个,体积为 viv_i 。

给定整数集合 SS,从这 nn 种物品中选出 k(k∈S)k(k\in S) 种物品,每种物品选任意正整数个,问可以得到哪些不超过 LL 的总体积值。

输入格式

从标准输入读入。

第一行两个正整数 n,L。

接下来n行,第 ii 行的两个数分别表示 ci,vic_i,v_i 。

接下来一行一个正整数 m,表示 ∣S∣|S|。

接下来一行m个互不相同的数,表示集合S的元素。

输出格式

输出到标准输出。

一行,按照从小到大的顺序输出可以得到的总体积值,相邻数之间用空格间隔。

输入样例

3 10
1 1
2 4
2 1
2
1 3

输出样例

1 2 4 6 7 8 10

数据范围

本题打包测评;对于 i>1i>1,子任务 ii 依赖子任务 i−1i-1。

子任务1(10分): 1≤n,ci,L,vi≤101\leq n,c_i,L,v_i\leq 10

子任务2(20分): 1≤n,ci,L≤1001\leq n,c_i,L\leq 100

子任务3(20分): 1≤n,ci,L≤2001\leq n,c_i,L\leq 200

子任务4(20分): 1≤n,ci,L≤5001\leq n,c_i,L\leq 500

子任务5(30分): 无特殊限制。

对于所有的数据,满足 $1\leq n,c_i,L\leq 10 ^ 3, 1\leq v_i\leq 10^2,1\leq m,S中的元素\leq n$。

原题面:statements.md。