Tý có \(N\) quả bóng xếp thành một hàng ngang. Quả bóng thứ \(i\) có giá trị \(a_i\). Khi bạn chọc quả bóng thứ \(i\), bạn nhận được \(a_{i-1} imes a_i imes a_{i+1}\) điểm. Sau khi chọc, quả bóng biến mất và các quả bóng còn lại xích lại gần nhau. Bạn có thể chọc các quả bóng theo thứ tự bất kỳ. Hãy tìm tổng điểm lớn nhất có thể nhận được. Quy ước \(a_0 = a_{N+1} = 1\).

Yêu cầu: Tính tổng điểm tối đa.

Đị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

Đầu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 500\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^5\)).

Đầu ra

• In ra một số nguyên duy nhất là tổng điểm lớn nhất.

Ví dụ

Đầu vào:

4
3 1 5 8

Đầu ra:

167

Giải thích

Thứ tự chọc tối ưu: chọc quả thứ 2 (giá trị 1) trước, sau đó chọc quả thứ 4 (giá trị 8), rồi quả thứ 1 (giá trị 3), cuối cùng quả thứ 3 (giá trị 5). Tổng điểm: \(3 imes 1 imes 5 + 3 imes 5 imes 8 + 1 imes 3 imes 8 + 1 imes 5 imes 1 = 15+120+24+8=167\).

Subtask