← 返回题目列表

AtCoder · tessoku_book_eo

B68. ALGO 快递

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

配点: 1000 点

問題文

ALGO 列车有 有 N 站, 它们的编号最大为1 减去 N 。目前,ALGO Railway 计划开设特快列车。N 站数 必须将 0 或更多指定为快车站。这里,车站 如果指定 i 为特快车站, P_i 您的预期利润为日元 (P_i 也可以是负数)。
另一方面,在创建特急列车时,用户询问 M 建议已提交。j 第二个提案是“站 如果将 A_j 指定为特快车站,则该车站 B_j 也应该被指定为特快车站。”如果您遵循所有建议,您能获得的最大利润是多少?

制約

  • 2 \leq N \leq 150
  • 1 \leq M \leq 150
  • |P_i| \leq 150
  • 1 \leq A_j , B_j \leq N
  • A_j \neq B_j
  • j\neq k 如果 (A_j,B_j) \neq (A_k,B_k)
  • 所有输入均为整数

入力

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

N M
P_1 \ldots P_N
A_1 B_1
\vdots
A_M B_M

出力

请以整数形式输出您可以赚取的最大利润。 将


入力例 1

5 2
3 4 -1 -5 5
1 3
2 4

出力例 1

7

駅 1、駅 3、駅 5 指定为快车站将增加利润。 7 日元,这是最大值。