Gần như toàn bộ vương quốc Byteland được bao phủ bởi rừng và sông. Các con sông nhỏ hợp lại thành những con sông lớn hơn; những con sông này lại tiếp tục hợp dòng, cho đến khi tất cả cùng chảy vào một con sông lớn. Con sông lớn đổ ra biển gần Bytetown.

Byteland có \(n\) ngôi làng của những người đốn gỗ, mỗi làng nằm gần một con sông. Hiện tại, Bytetown có một xưởng cưa lớn xử lý toàn bộ cây gỗ được chặt trong vương quốc. Các cây gỗ được thả trôi từ các làng theo dòng sông đến xưởng cưa ở Bytetown. Nhà vua quyết định xây thêm \(k\) xưởng cưa tại các làng để giảm chi phí vận chuyển gỗ xuôi dòng. Sau khi xây các xưởng cưa, gỗ không cần trôi tới Bytetown mà có thể được xử lý tại xưởng cưa đầu tiên gặp trên đường xuôi dòng. Gỗ được chặt gần một làng có xưởng cưa không cần vận chuyển bằng đường sông. Các con sông ở Byteland không phân nhánh theo chiều dòng chảy, nên từ mỗi làng chỉ có đúng một đường xuôi dòng tới Bytetown.

Các kế toán của nhà vua đã tính được số cây gỗ được chặt hằng năm ở mỗi làng. Bạn phải quyết định vị trí xây các xưởng cưa để tổng chi phí vận chuyển gỗ trong một năm nhỏ nhất. Chi phí vận chuyển bằng đường sông là một xu cho mỗi kilômét, đối với mỗi cây gỗ.

Cho số làng, số xưởng cưa cần xây thêm, số cây gỗ được chặt gần mỗi làng và mô tả các dòng sông, hãy viết chương trình tính chi phí vận chuyển nhỏ nhất sau khi xây thêm các xưởng cưa.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(n\) và \(k\): số làng không kể Bytetown và số xưởng cưa cần xây thêm. Các làng được đánh số từ \(1\) đến \(n\); Bytetown mang số \(0\).
• Mỗi dòng trong \(n\) dòng tiếp theo chứa ba số nguyên cách nhau bởi một dấu cách. Dòng thứ \(i+1\) chứa \(w_i\), \(v_i\), \(d_i\), theo thứ tự này.

Trong đó, \(w_i\) là số cây gỗ được chặt gần làng \(i\) mỗi năm; \(v_i\) là ngôi làng đầu tiên, hoặc Bytetown, gặp khi đi xuôi dòng từ làng \(i\); còn \(d_i\) là khoảng cách theo đường sông từ làng \(i\) đến \(v_i\), tính bằng kilômét.

Dữ liệu bảo đảm rằng tổng chi phí thả trôi toàn bộ số cây gỗ được chặt trong một năm tới xưởng cưa ở Bytetown không vượt quá \(2\,000\,000\,000\) xu.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên: chi phí vận chuyển gỗ bằng đường sông nhỏ nhất trong một năm, tính bằng xu.

Ràng buộc

• \(2 \le n \le 100\).
• \(1 \le k \le 50\) và \(k \le n\).
• \(0 \le w_i \le 10\,000\) với \(1 \le i \le n\).
• \(0 \le v_i \le n\) với \(1 \le i \le n\).
• \(1 \le d_i \le 10\,000\) với \(1 \le i \le n\).

Phân nhóm

Trong \(50\%\) số bộ dữ liệu kiểm tra, \(n\) không vượt quá \(20\).

Ví dụ

4 2
1 0 1
1 1 10
10 2 5
1 2 3

4

Nguồn

IOI 2005, ngày thi thứ hai: Rivers, bản tiếng Anh 1.04. Tác giả đề bài: Łukasz Kowalik. Tập đề bài và lời giải IOI 2005.