Một người chào hàng lên kế hoạch xây dựng hành trình đi qua đúng \(4\) thành phố phân biệt. Qua khảo sát, trong vùng lãnh thổ gồm \(n\) thành phố tiềm năng, được đánh số từ \(1\) đến \(n\), thành phố thứ \(i\) có thể thu được lợi nhuận là \(a_i\). Hệ thống giao thông trong vùng gồm \(m\) tuyến đường hai chiều khác nhau, tuyến đường thứ \(j\) (\(j = 1, 2, \dots, m\)) cho phép đi lại giữa thành phố \(u_j\) và thành phố \(v_j\). Người chào hàng muốn tìm hành trình để tổng lợi nhuận có thể thu được tại \(4\) thành phố đi qua là lớn nhất.

Input

• Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(m\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_i\) (\(a_i \leq 10^9\)).
• Dòng thứ \(j\) trong số \(m\) dòng tiếp theo chứa hai số nguyên dương \(u_j, v_j\) cho biết thông tin về tuyến đường thứ \(j\). Giả thiết là \(u_j \neq v_j, j = 1, 2, \dots, m\).

Output

• Ghi một số nguyên duy nhất là tổng lợi nhuận lớn nhất thu được. Quy ước: Ghi số \(-1\) nếu không tìm được hành trình thoả mãn yêu cầu đặt ra.

Example

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

8

Constraints

• \(n \leq 10^6, m \leq 10^6\).
• \(a_i \leq 10^9\).
• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 100\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Nguồn: 3D'21