Khi tới San Fierro, thì CJ muốn đi du lịch quanh thành phố cho thoả thích, với lại để thăm quan nơi đây. CJ có được tấm bản đồ thành phố mà trước ông The Truth có đưa cho anh.

Thành phố San Fierro có \(N\) địa điểm nổi tiếng mà CJ muốn đến, được đánh số từ \(1\) tới \(N\), và \(M\) con đường hai chiều, được đánh số từ \(1\) tới \(M\). Vì CJ chỉ có \(4\) ngày nghỉ ngơi nên CJ quyết định lập hành trình du lịch gồm \(4\) địa điểm nổi tiếng khác nhau \(A_{1},A_{2},A_{3},A_{4}\) sao cho có đường nối trực tiếp giữa \(A_{1}\) với \(A_{2}\), \(A_{2}\) với \(A_{3}\), \(A_{3}\) với \(A_{4}\), và mỗi địa điểm trong \(4\) địa điểm được chọn thăm đúng một lần và không đi tới các địa điểm nổi tiếng khác mà không nằm trong danh sách \(4\) điểm được chọn.

Vì CJ muốn được thoải mái, sảng khoái tinh thần nhất có thể để làm việc, nên CJ đã tham khảo trên bản đồ tất cả các địa điểm nổi tiếng trên. Và mỗi địa điểm sẽ cho CJ độ sảng khoái tinh thần là \(C_{i}\). Hãy giúp CJ lập ra hành trình sao cho tổng độ sảng khoái tinh thần là cao nhất có thể.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N,M\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(C_{1},C_{2},…,C_{N}\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(u_{i},v_{i}\).

Output

• Gồm 2 dòng:
• Dòng đầu tiên ghi ra tổng độ sảng khoái tinh thần cao nhất có thể.
• Dòng thứ hai ghi ra số hiệu của \(4\) địa điểm \(A_{1},A_{2},A_{3},A_{4}\) theo thứ tự hành trình. Dữ liệu đảm bảo CJ có thể chọn \(4\) địa điểm trên hành trình.

Constraints

• \(1 \leq N \leq 10^{5}\), \(1 \leq M \leq 3.10^{5}\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^{2}\), \(M \leq 3.10^{2}\).
• Subtask \(2\) (\(70\%\) số điểm): Không có ràng buộc gì thêm.

Example

6 6
7 8 1 1 7 1 
1 3
4 2
1 6
4 6
5 1
3 5 

17
2 4 6 1