D - 集装箱中转

得分： $400$ 分

题目描述

我们有 $N$ 件称为 Baggage $1$ 到 $N$ 的行李和 $M$ 个称为 Box $1$ 到 $M$ 的集装箱。

行李 $i$ 的大小为 $W_i$ ，价值为 $V_i$。

Box $i$ 可以装下大小不超过 $X_i$ 的行李，它不能容纳两件或更多行李。

你将得到 $Q$ 个查询。在每个查询中，给定两个整数 $L$ 和 $R$，解决以下问题：

• 问题：在 $M$ 个箱子中，有 $R-L+1$ 个箱子，即 Box $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$ 行应包含 $\mathrm{Query}_i$ 描述问题的答案。

---

3 4 3
1 9
5 3
7 8
1 8 6 9
4 4
1 4
1 3

20
0
9

在第一个查询中，只有 Box $4$ 不可用。 将行李 $1$ 放入 Box $1$，将行李 $3$ 放入 Box $2$，将行李 $2$ 放入 Box $3$，我们可以将所有行李放入箱子中，使得箱子中行李的总价值为 $20$。

在第二个查询中，所有箱子都不可用，答案为 $0$。

在第三个查询中，只有 Box $4$ 可用。将行李 $1$ 放入 Box $4$，我们可以将箱子中行李的总价值最大值设置为 $9$。