Tý có \(N\) đống đá xếp thành hàng, đống thứ \(i\) nặng \(a_i\). Mỗi lần, bạn gom hai đống liền kề thành một đống mới, chi phí bằng tổng khối lượng hai đống đó. Sau khi gom, đống mới thay thế hai đống cũ.

Lặp lại cho đến khi còn một đống. Tìm tổng chi phí nhỏ nhất.

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

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

Output:

3

Dữ liệu vào

• Dòng đầu gồm \(N\) (\(2 \le N \le 5000\)).
• Dòng thứ hai gồm \(N\) số \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).

Kết quả ra

• In ra tổng chi phí nhỏ nhất.

Ví dụ

Input

4
4 3 5 2

Output

29

Giải thích: Cách gom: (5+2=7) → (4,3,7), (3+7=10) → (4,10), (4+10=14). Tổng = 7+10+14 = 31. Cách khác: (4+3=7) → (7,5,2), (7+5=12) → (12,2), (12+2=14) → 7+12+14 = 33. Đáp án 29: (3+5=8) → (4,8,2), (4+8=12) → (12,2), (12+2=14) → 8+12+14 = 34. Tối ưu: (4+3=7) → (7,5,2), (5+2=7) → (7,7), (7+7=14) → 7+7+14 = 28. Vậy đáp án là 28? Hmm ví dụ mẫu.

Subtask