← 返回题目列表

AtCoder · abc195_d

D. 航运中心

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

我们有 N 称为 Baggage 的行李件数 1 通过 N,和 M 名为 Box 的盒子 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
\vdots
W_N V_N
X_1 \ldots X_M
\mathrm{Query}_1
\vdots
\mathrm{Query}_Q

每个查询均采用以下格式:

L R

输出

打印 Q 行。

的 i-th 行应包含所描述问题的答案 \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

在 1-st 查询,仅限 Box 4 不可用。 通过放置行李 1 放入盒子 1, 行李 3 放入盒子 2和行李 2 放入盒子 3,我们可以将所有行李放入箱子中,使得箱子中行李的总价值 20.

在 2-nd查询,所有框都不可用;答案是 0.

在 3-rd 查询,仅 Box 4 可用。通过放置行李 1 放入盒子 4,我们可以计算箱子中行李的总价值 9,这是最大可能的结果。