Tý có một nhà máy có \(N\) công đoạn sản xuất. Để ghép các công đoạn thành một dây chuyền, người ta thực hiện: chọn một điểm chia \(k\), ghép đoạn \([l, k]\) với đoạn \([k, r]\). Chi phí ghép đoạn \([l, r]\) là tổng chi phí vận hành của các công đoạn trong đoạn, ký hiệu \(S(l,r) = a_l + a_{l+1} + \dots + a_{r-1}\).

Tổng chi phí để ghép toàn bộ \(N\) công đoạn là tổng chi phí ghép của mọi bước. Hãy tìm tổng chi phí nhỏ nhất để ghép \(N\) công đoạn thành mộ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 chi phí nhỏ nhất.

Ví dụ

Input

4
1 3 5 2

Output

28

Subtask