题目描述

我们有 $N$ 个被称为 Baggage $1$ 到 $N$ 的行李和 $M$ 个被称为 Box $1$ 到 $M$ 的箱子。

第 $i$ 个行李的尺寸为 $W_i$，价值为 $V_i$。

第 $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$ $Query_1$ $\vdots$ $Query_Q$

每个 Query 的格式如下：

$L$ $R$

输出

打印 $Q$ 行。

第 $i$ 行应该包含 $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

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

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

在第三个查询中，只有 Box $4$ 可用。通过将 Baggage $1$ 放入 Box $4$，我们可以使箱子中行李的总价值达到 $9$，这是最大可能的结果。