You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1686 题。

题目描述

游戏中有 $n$ 个房间，和 $m$ 条隧道连接它们。每个房间中有一定数量的金币。你可以自由选择起始房间和结束房间，问题是：在通过隧道时，最多能收集到多少金币？

输入格式

第一行包含两个整数 $n$ 和 $m$：分别表示房间的数量和隧道的数量。房间编号为 $1,2,…,n$。

接下来的一行包含 $n$ 个整数 $k_1,k_2,…,k_n$：表示每个房间中的金币数量。

接下来有 $m$ 行，每行描述一条隧道。每行包含两个整数 $a$ 和 $b$：表示从房间 $a$ 到房间 $b$ 有一条单向隧道。

输出格式

输出一个整数：表示你能收集到的最大金币数。

样例

4 4
4 5 2 7
1 2
2 1
1 3
2 4

16

说明/提示

$1 \leq n \leq 10^5$；

$1 \leq m \leq 2 \cdot 10^5$；

$1 \leq k_i \leq 10^9$；

$1 \leq a, b \leq n$。