#P17743. 背包
背包
题目描述
有 种物品,第 种物品有 个,体积为 。
给定整数集合 ,从这 种物品中选出 种物品,每种物品选任意正整数个,问可以得到哪些不超过 的总体积值。
输入格式
从标准输入读入。
第一行两个正整数 n,L。
接下来n行,第 行的两个数分别表示 。
接下来一行一个正整数 m,表示 。
接下来一行m个互不相同的数,表示集合S的元素。
输出格式
输出到标准输出。
一行,按照从小到大的顺序输出可以得到的总体积值,相邻数之间用空格间隔。
输入样例
3 10
1 1
2 4
2 1
2
1 3
输出样例
1 2 4 6 7 8 10
数据范围
本题打包测评;对于 ,子任务 依赖子任务 。
子任务1(10分):
子任务2(20分):
子任务3(20分):
子任务4(20分):
子任务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。