← 返回题目列表

AtCoder · kupc2019_b

B. 背包问题

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

配点 : 200 点

問題文

n 项, 它们的编号最大为1 从 n 。

每件物品都有价值和重量,i 项的值为 v_i,重量为 w_i 。

您可以计算这些物品的总重量。 我想选择一些项目,以免超过 W 并最大化所选项目的总价值。

但是, 有m 条件。 第

j 个条件是 分别是 (a_j, b_j) 。 如果您选择 a_j 项目, 您必须选择 b_j 项目, 您必须选择b_j 项目, 您必须选择 a_j 项目。” 这就是它的意思。

满足所有这些条件后,n 物品的重量总和为 选择多项且不超过 W 时,求值之和的最大值。

制約

  • 所有输入值都是整数。
  • 1 \leq n \leq 100
  • 0 \leq m \leq \frac {n(n-1)}{2}
  • 1 \leq W \leq 10^4
  • 1 \leq w_i \leq W
  • 1 \leq v_i \leq 10^7
  • 1 \leq a_i, b_i \leq n
  • a_i \neq b_i
  • i \neq j 然后, 满足所有(a_i, b_i) \neq (a_j, b_j) 和 满足 (a_i, b_i) \neq (b_j, a_j)

入力

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

n m W
w_1 v_1
w_2 v_2
\vdots
w_n v_n
a_1 b_1
a_2 b_2
\vdots
a_m b_m

出力

m 条件后, 选择多个项目时打印数值总和的最大值,以免超过n 物品的重量总和为 选择多项且不超过 W 。


入力例 1

3 1 10
3 2
5 4
3 3
1 2

出力例 1

6

1 第一项和 通过选择第 2 项,我们计算值的总和。 6 ,这是最佳的。

从条件来看, 请注意,您不能仅选择2 第一项和 通过选择第 3 项目。


入力例 2

4 0 10
1 1
2 2
3 3
4 4

出力例 2

10

您可以选择所有项目。


入力例 3

3 3 6
2 5
3 8
3 4
1 2
2 3
3 1

出力例 3

0

我无法选择任何项目。


入力例 4

1 0 10000
10000 10000000

出力例 4

10000000