Kim Ngân đã khám phá ra một bản đồ kho báu cổ xưa dẫn đến một hệ thống hang động phức tạp nằm sâu dưới lòng đất. Hệ thống này bao gồm \(n\) phòng và \(m\) đường hầm một chiều nối liền các phòng với nhau.

Trong mỗi phòng, Kim Ngân phát hiện ra một số lượng vàng nhất định. Phòng thứ \(i\) chứa \(A_i\) đồng xu vàng. Kim Ngân có thể thu thập số vàng này mỗi khi cô đến thăm phòng. Điều thú vị là cô có thể thăm lại bất kỳ phòng nào nhiều lần.

Nhiệm vụ của Kim Ngân là tìm ra con đường tối ưu để thu thập được số lượng vàng nhiều nhất có thể. Cô có thể bắt đầu hành trình của mình từ bất kỳ phòng nào và cũng có thể kết thúc ở bất kỳ phòng nào trong hệ thống hang động.

Vậy, số lượng vàng lớn nhất mà Kim Ngân có thể thu thập được trong chuyến phiêu lưu của mình là bao nhiêu?

Dữ liệu vào

• Dòng đầu tiên gồm \(2\) số nguyên \(n,m\).
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\).
• \(m\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(u,v\), có đường hầm từ \(u\) đến \(v\).

Dữ liệu ra

• In ra lượng xu vàng lớn nhất cô có thể lấy được.

Ràng buộc

• \(1 \le n,m \le 10^5\)
• \(1 \le A_i \le 10^9\)
• \(1 \le u,v \le n\)

Input 1

3 3
1 2 3
1 2
2 3
3 1

Output 1

6