行李与箱子

题目描述

有编号为 $1$ 到 $N$ 的 $N$ 件行李和编号为 $1$ 到 $M$ 的 $M$ 个箱子。

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

箱子 $i$ 可以放入大小在 $X_i$ 以下的行李。$1$ 个箱子不能放入 $2$ 件以上的行李。

给定 $Q$ 个询问。每个询问给出两个整数 $L,R$,请解决以下问题。

• 问题:在 $M$ 个箱子中,箱子 $L, L+1, \ldots, 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$ 对应的问题的答案。

样例

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

20
0
9

在第 $1$ 个询问中箱子 $4$ 不能使用。 将行李 $1$ 放入箱子 $1$,行李 $3$ 放入箱子 $2$,行李 $2$ 放入箱子 $3$,可以把所有行李放入箱子中,箱子中行李的价值总和可以达到 $20$。

在第 $2$ 个询问中所有箱子都不能使用。因此答案是 $0$。

在第 $3$ 个询问中只有箱子 $4$ 可以使用。将行李 $1$ 放入箱子 $4$,箱子中行李的价值总和为 $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$
• 输入均为整数