Một trò chơi có \(n\) phòng và \(m\) đường hầm giữa chúng. Mỗi phòng đều có một số lượng đồng xu nhất định. Số lượng đồng xu tối mà đa bạn có thể thu thập được khi đi qua các đường hầm là bao nhiêu nếu bạn có thể tự do lựa chọn phòng bắt đầu và kết thúc của mình?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\) \((1 \leq n \leq 10^{5}, 1 \leq m \leq 2 \times 10^{5})\) - số lượng phòng và đường hầm. Các phòng được đánh số \(1, 2, \ldots, n\).
• Sau đó, có \(n\) số nguyên \(k_{1}, k_{2}, \ldots, k_{n}\) \((1 \leq k_{i} \leq 10^{9})\) - số lượng đồng xu trong mỗi phòng.
• Cuối cùng, có \(m\) dòng mô tả các đường hầm. Mỗi dòng có hai số nguyên \(a\) và \(b\) \((1 \leq a, b \leq n)\) - có một đường hầm từ phòng \(a\) đến phòng \(b\). Mỗi đường hầm là một đường hầm một chiều.

Output

• In một số nguyên: số lượng đồng xu tối đa bạn có thể thu thập.

Example

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

16