Tý có đa giác lồi \(N\) đỉnh, đỉnh \(i\) có trọng số \(w_i\). Chia đa giác thành các tam giác bằng cách vẽ các đường chéo không cắt nhau. Chi phí một tam giác \((i, j, k)\) là \(w_i + w_j + w_k\). Tìm tổng chi phí nhỏ nhất của phép chia.

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

Ràng buộc