题目描述
小杨开了家网店，卖 种商品：第 种每件重 、价值 ，每种都货源管够，想卖几件卖几件。店里的纸箱最大能装 千克，小杨想先把容量为 到 的每种纸箱最多能装下多少价值都算好，再回答 位顾客的询问：第 位顾客问一个容量 ，请输出这个容量下能装下的最大总价值。
输入格式
第一行两个整数 、。
接下来 行，每行两个整数 、。
接下来一行一个整数 。
最后一行 个整数 。
输出格式
一行 个整数，第 个整数表示 ，用空格分隔。
样例
输入 1
2 9
2 3
4 5
5
1 3 5 8 9
输出 1
0 3 6 12 12
容量 时只有一包第一种装得下，价值 ；容量 时两包第一种得 ，比一包第二种的 更多；容量 时四包第一种得 ；容量 还空出 ，答案仍是 。
数据范围
，，，，，。答案不超过 。