Tý có \(N\) mảnh đất hình chữ nhật, mảnh \(i\) rộng \(w_i\), cao \(h_i\). Chủ đất muốn bán hết tất cả các mảnh. Mỗi lần mua, người mua có thể mua một nhóm các mảnh đất, giá nhóm bằng:

\[(\text{chiều rộng lớn nhất trong nhóm}) \times (\text{chiều cao lớn nhất trong nhóm})\]

Hãy chia các mảnh đất thành các nhóm (mỗi mảnh một nhóm, thứ tự tùy ý) sao cho tổng tiền thu được là nhỏ nhất (giả sử người mua luôn mua hế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\) (\(1 \le N \le 10^5\)).
• \(N\) dòng sau, mỗi dòng \(w_i, h_i\) (\(1 \le w_i, h_i \le 10^6\)).

Kết quả ra

• In ra tổng tiền nhỏ nhất.

Ví dụ

Input

4
2 5
4 3
3 6
1 4

Output

27

Giải thích: Sắp xếp (4,3), (2,5), (3,6), (1,4). Nhóm (4,3)+(2,5): \(max_w=4\), \(max_h=5\) → 20. Nhóm (3,6)+(1,4): \(max_w=3\), \(max_h=6\) → 18. Tổng 38. Tối ưu: (4,3) riêng 12, (2,5)+(3,6)+(1,4): \(max_w=3\), \(max_h=6\) → 18, tổng 30. Đáp án 27.

Subtask