Trong một màn pháo hoa, mọi khối thuốc nổ nối với bộ kích nổ bằng các dây cháy phải nổ đồng thời. Các dây được nối thành một cây. Tia lửa bắt đầu ở bộ kích nổ, đi dọc dây với vận tốc không đổi; khi đến một nút nối, nó lan ra mọi dây con.

Hình 1 cho thấy cách nối sáu khối thuốc nổ \(E_1,\ldots,E_6\), chiều dài các dây và thời điểm nổ khi tia lửa bắt đầu tại thời điểm \(0\).

{{asset:apio16-fireworks-layout}}

Bạn được phép thay đổi chiều dài các dây, kể cả giảm một dây xuống \(0\) mà vẫn giữ nguyên quan hệ nối của cây. Chi phí thay đổi một dây là trị tuyệt đối của hiệu giữa chiều dài mới và chiều dài ban đầu.

Hình 2 minh họa hai phương án làm tất cả khối thuốc nổ của Hình 1 nổ cùng lúc. Phương án bên trái cho chúng nổ tại thời điểm \(13\) với tổng chi phí \(6\); phương án bên phải cho chúng nổ tại thời điểm \(14\) với tổng chi phí \(5\).

{{asset:apio16-fireworks-adjustments}}

Hãy tìm tổng chi phí nhỏ nhất để mọi khối thuốc nổ phát nổ cùng một thời điểm.

Dữ liệu vào

Dòng đầu chứa hai số nguyên dương \(N,M\), trong đó \(N\) là số nút nối và \(M\) là số khối thuốc nổ. Các nút nối được đánh số từ \(1\) đến \(N\); nút \(1\) đặt bộ kích nổ. Các khối thuốc nổ tương ứng với các đỉnh từ \(N+1\) đến \(N+M\).

Với mỗi đỉnh \(i=2,3,\ldots,N+M\), có một dòng chứa hai số nguyên \(P_i,C_i\). Đỉnh \(i\) được nối với đỉnh cha \(P_i\), và dây đó có chiều dài \(C_i\).

Dữ liệu ra

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

Ràng buộc

• \(1\le P_i<i\).
• \(1\le C_i\le10^9\).
• Tổng số dây nối với mọi nút nối khác nút đặt bộ kích nổ lớn hơn \(1\).
• Mỗi đỉnh thuốc nổ là một lá của cây.
• \(1\le N,M\) và \(N+M\le300\,000\).

Ví dụ

4 6
1 5
2 5
2 8
3 3
3 2
3 3
2 9
4 4
4 3

5

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2016, bài Fireworks.