← 返回题目列表

AtCoder · nadafes2022_day1_e

E. 偶数度

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

配点 : 400 点

問題文

N 頂点 M 给出了一个简单的无向边图。
在顶点 1, \dots, N 已编号,并且顶点 i \, (1 \leq i \leq N) 是一个整数 连接 A_i 。
另外, 请注意,不得访问i \, (1 \leq i \leq M) 第一条边是顶点 B_i 和顶点 连接 C_i 。

KoD 您可以从图表中选择任何数字(0 选择书本(或一本书)的边缘并将其移除。
KoD 你得到分数 将定义为运算后图中偶数度顶点写入的整数之和。但是,如果操作后没有偶数顶点,则得分为 0 。

KoD 找出你可以获得的最大可能分数。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • |A_i| \leq 10^9 \, (1 \leq i \leq N)
  • 1 \leq B_i \lt C_i \leq N \, (1 \leq i \leq M)
  • (B_i, C_i) \neq (B_j, C_j) \, (i \neq j)
  • 所有输入均为整数。

入力

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

N M
A_1 \ldots A_N
B_1 C_1
\vdots
B_M C_M

出力

打印答案。 求解


入力例 1

3 2
-10 2 3
1 2
2 3

出力例 1

3

2 条边后,顶点 只有 3 的度数为偶数,所以你得到的分数是 3 。

分数 它不能超过 4 ,所以答案是 3 。


入力例 2

4 2
1 2 3 -100
1 3
2 3

出力例 2

-94

给定的图不一定是连通的。