Tại Earth-2729, có ~n~ quốc gia, quốc gia thứ ~i~ có sức mạnh quân sự ~c_i~. Hiện tại, đang có ~m~ cuộc xung đột quân sự diễn ra trên toàn cầu, cuộc xung đột thứ ~i~ giữa hai quốc gia ~u_i~ và ~v_i~.

Nhóm Azenzers muốn có những động thái để tránh tình hình chiến sự leo thang, tuy nhiên đây không phải là truyện tranh Marvel, họ không hề có siêu năng lực nào cả. Vậy nên nhóm muốn thành lập một liên minh gồm một số quốc gia để hợp tác quân sự, sao cho tổng sức mạnh quân sự của các nước này là lớn nhất và không có cuộc xung đột nào đang diễn ra giữa các quốc gia được lựa chọn để hợp tác.

Hãy giúp nhóm Azenzers tìm được liên minh quân sự tốt nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n,m~ .

• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~c_i~ là sức mạnh quân sự của từng quốc gia .

• Trong ~m~ dòng sau, mỗi dòng gồm hai số nguyên dương ~u_i, v_i~ miêu tả xung đột thứ ~i~.

Output

• Gồm một số nguyên dương miêu tả tổng sức mạnh quân sự lớn nhất của liên minh thỏa mãn.

Constraints

• ~1 \le n \le 40, 0 \le m \le \frac{n \times (n-1)}{2}~
• ~1 \le c_i \le 10^9~
• ~1 \le u_i,v_i \le n; u_i \neq v_i~

Subtask

• Subtask ~1~ (~20~ điểm): ~n \le 20~
• Subtask ~2~ (~30~ điểm): ~n \le 30~
• Subtask ~3~ (~50~ điểm): không có ràng buộc gì thêm.

Sample Input 1

4 2
4 9 2 1
1 4
2 4

Sample Output 1

15

Explannation 1

• Chọn quốc gia ~1~, ~2~ và ~3~.

Messi đang muốn đi tập Gym để chụp hình đăng Instagram. Phòng Gym của anh có ~n~ quả tạ được đánh số từ ~1~ tới ~n~. Quả tạ thứ ~i~ có trọng lượng ~w_i~.

Vì là GOAT, Messi có thể nâng nhiều tạ một lúc, tuy nhiên, các tạ mà anh ấy chọn sẽ phải tuân thủ điều kiện sau:

• Đối với mọi chữ số từ ~0~ tới ~9~, số lần chữ số đó xuất hiện trong các tạ được chọn không vượt quá ~2~.

Ví dụ, Messi có thể nâng các tạ ~[10,8,1]~ nhưng không thể nâng tạ ~[700,70]~ vì số ~0~ lặp lại ~3~ lần.

Vì muốn có một cơ bắp nhìn quá là ưng, hãy in ra trọng lượng tối đa của các tạ mà Messi có thể mang.

Input

• Dòng đầu tiên gồm số hai nguyên dương ~n~ ~(1\le n \le 100)~
• Dòng thứ hai gồm ~n~ số nguyên dương miêu tả dãy ~w~ ~(1 \le w_i \le 10^9)~.

Output:

• In ra kết quả của bài toán.

Sample Input 1

4
99 9 58 72

Sample Output 1

229

Sample Input 2

1
777

Sample Output 2

0

Tèo cảm thấy bài toán mà Tí giải ở trên quá đơn giản nên thách đố thêm bài toán sau. Thay vì đặt các viên ngọc trên đường thẳng, Tèo đặt chúng lên một cái cây (đồ thị liên thông vô hướng và không có chu trình). Để đơn giản, Tèo chỉ chọn ra các viên ngọc thuộc một trong 4 màu: đỏ, xanh, lục, vàng.

Tèo muốn chia nhỏ cây thành các thành phần liên thông bằng cách bỏ đi vài cạnh. Đồng thời Tèo không muốn thấy thành phần liên thông nào chứa ba màu đỏ, xanh, lục cùng lúc (vì theo Tèo, chúng làm mất vẻ đẹp của nhau). Nhiệm vụ của Tí là đếm xem có bao nhiêu bỏ đi một vài cạnh của cây (có thể không bỏ cạnh nào) sao cho trong các thành phần liên thông còn lại, không có thành phần liên thông nào chứa cả 3 màu đỏ, xanh, lục.

Hai cách chia được xem là khác nhau nếu có một cạnh bị bỏ trong cách chia này mà không bị bỏ trong cách chia còn lại.

Yêu cầu: In ra số cách chia sau khi ~\mod 10^9+7~

Input

• Dòng đầu tiên là số tự nhiên ~n\ (n\leq 3\cdot 10^5)~ chỉ số viên ngọc.
• Dòng thứ hai chứa một xâu miêu tả màu các viên ngọc. Chữ cái thứ ~i~ trong xâu tương ứng với màu của viên ngọc thứ ~i~ (D: Đỏ, X: Xanh, L: Lục, V: Vàng)
• ~n-1~ dòng tiếp theo chứa hai số nguyên ~u,v~ (~1 ≤ u,v ≤ n~) miêu tả một cạnh nối viên ngọc thứ ~u~ và thứ ~v~.
• Dữ liệu đảm bảo đồ thị là một cây.

Output

• Ghi ra một số nguyên duy nhất - số cách chia.

Scoring

• Subtask ~1~ (~30\%~ số điểm): Cây là đường thẳng, các cạnh trên cây có dạng (~i,i+1~) với (~0<i<n~) .</li>
• Subtask ~2~ (~30\%~ số điểm): Không có đỉnh nào màu đỏ.
• Subtask ~3~ (~40\%~ số điểm): Không có ràng buộc gì thêm.

Sample Input 1

 4
DXLV
1 2
2 3
3 4 

Sample Output 1

6

Explanation 1

• Các cách chia thỏa mãn là: ~(12)|(34), (1)|(234), (1)|(23)|(4), (1)|(2)|(3)|(4), (1)|(2)|(34), (12)|(3)|(4)~. Lưu ý các viên ngọc ~1, 2, 3~ không được xuất hiện trong cùng một thành phần liên thông.