分数: 400 点
问题陈述
我们有 N 称为 Baggage 的行李件数 1 通过 N,和 M 名为 Box 的盒子 1 通过 M.
行李 i 的大小为 W_i 和值为 V_i.
盒子 i 最多可容纳一件行李 X_i。它不能容纳两件或更多件行李。
你将得到 Q 查询。在每个查询中,给出两个整数 L 和 R,解决以下问题:
- 问题:超出 M 盒子, R-L+1 盒子,盒子 L,L+1,\ldots,R已变得不可用。 求出我们可以同时放入其余箱子中的一组行李的最大可能总价值。
约束
- 1 \leq N \leq 50
- 1 \leq M \leq 50
- 1 \leq Q \leq 50
- 1 \leq W_i \leq 10^6
- 1 \leq V_i \leq 10^6
- 1 \leq X_i \leq 10^6
- 1 \leq L \leq R \leq M
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M Q
W_1 V_1
\vdots
W_N V_N
X_1 \ldots X_M
\mathrm{Query}_1
\vdots
\mathrm{Query}_Q
每个查询均采用以下格式:
L R
输出
打印 Q 行。
的 i-th 行应包含所描述问题的答案 \mathrm{Query}_i.
示例输入 1
3 4 3 1 9 5 3 7 8 1 8 6 9 4 4 1 4 1 3
示例输出 1
20 0 9
在 1-st 查询,仅限 Box 4 不可用。 通过放置行李 1 放入盒子 1, 行李 3 放入盒子 2和行李 2 放入盒子 3,我们可以将所有行李放入箱子中,使得箱子中行李的总价值 20.
在 2-nd查询,所有框都不可用;答案是 0.
在 3-rd 查询,仅 Box 4 可用。通过放置行李 1 放入盒子 4,我们可以计算箱子中行李的总价值 9,这是最大可能的结果。