问题描述

我们有$N$件行李，分别称为行李$1$到行李$N$，以及$M$个箱子，分别称为箱子$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
...
W_N V_N
X_1 ... X_M
Query_1
...
Query_Q

每个查询的格式如下：

L R

输出

输出$Q$行。
第$i$行应包含对应查询$\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

在第一个查询中，只有箱子$4$不可用。
通过将行李$1$放入箱子$1$，行李$3$放入箱子$2$，行李$2$放入箱子$3$，我们可以将所有行李放入箱子中，使得箱子中行李的总价值为$20$。
在第二个查询中，所有箱子都不可用；答案为$0$。
在第三个查询中，只有箱子$4$可用。通过将行李$1$放入箱子$4$，我们可以使箱子中行李的总价值为$9$，这是可能的最大结果。