题目描述

$1$ 到 $N$ 的编号的 $N$ 个包裹和 $1$ 到 $M$ 的编号的 $M$ 个箱子。

包裹 $i$ 的大小是 $W_i$，价值是 $V_i$。

箱子 $i$ 可以放入大小为 $X_i$ 以下的包裹。一个箱子不能放入 $2$ 件或更多的包裹。

给定 $Q$ 个查询。每个查询包含 $2$ 个整数 $L,R$，请解决以下问题。

问题：在这 $M$ 个箱子中，区间 $[L,R]$ 的 $R-L+1$ 个箱子不能使用。求剩下的箱子中能放入的包裹的总价值的最大值。

输入格式

输入以以下格式从标准输入给出。

$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$ 对应的问题的答案。

样例 #1

样例输入 #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\ \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$

输入均为整数

样例解释 #1

在第 $1$ 个查询中，箱子 $4$ 不能使用。可以将包裹 $1$ 放入箱子 $1$，包裹 $3$ 放入箱子 $2$，包裹 $2$ 放入箱子 $3$，这样可以将所有包裹放入箱子中，并且使得箱子中的包裹总价值为 $20$。第 $2$ 个查询中，所有箱子都不能使用，因此答案为 $0$。在第 $3$ 个查询中，只有箱子 $4$ 可以使用。将包裹 $1$ 放入箱子 $4$，这样箱子中的包裹总价值为 $9$，为最大值。