该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

有 $N$ 个编号为 $1 \sim N$ 的行李，以及 $M$ 个编号为 $1 \sim M$ 的箱子。

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

第 $i$ 个箱子最多可以装一个大小不超过 $X_i$ 的行李。

现在给出 $Q$ 个查询，每个查询给出两个整数 $L, R$：

• 在 $M$ 个箱子中，编号在区间 $[L, R]$ 内的 $R - L + 1$ 个箱子无法使用。请你求出在剩余可用箱子中，能够同时放入的行李的最大总价值。

输入格式

第一行输入三个整数 $N, M, Q$。

接下来输入 $N$ 行，第 $i$ 行包含两个整数 $W_i, V_i$，分别表示第 $i$ 个行李的大小和价值。

接下来输入一行 $M$ 个整数 $X_1, X_2, \ldots, X_M$，表示每个箱子的最大容纳大小。

接下来输入 $Q$ 行，每行包含两个整数 $L, R$，表示一个查询。

输出格式

输出共 $Q$ 行，每行一个整数，第 $i$ 行输出第 $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 解释：

• 查询 1（$L=4, R=4$）：箱子 $4$ 不可用，剩余箱子容量为 $[1, 8, 6]$。将行李 $1$ 放入箱子 $1$，行李 $3$ 放入箱子 $2$，行李 $2$ 放入箱子 $3$，总价值为 $9 + 8 + 3 = 20$。
• 查询 2（$L=1, R=4$）：所有箱子均不可用，能够放入的最大总价值为 $0$。
• 查询 3（$L=1, R=3$）：仅箱子 $4$（容量 $9$）可用。放入行李 $1$（大小 $1$，价值 $9$），最大总价值为 $9$。

评测数据规模

对于所有评测数据：

• $1 \leq N \leq 50$
• $1 \leq M \leq 50$
• $1 \leq Q \leq 50$
• $1 \leq W_i \leq 10^6 \quad (1 \leq i \leq N)$
• $1 \leq V_i \leq 10^6 \quad (1 \leq i \leq N)$
• $1 \leq X_i \leq 10^6 \quad (1 \leq i \leq M)$
• $1 \leq L \leq R \leq M$
• 所有输入均为整数