Di dời

Thành phố X sắp phải đối mặt với một thảm họa thiên nhiên, nên cần di dời toàn bộ người dân ra khỏi thành phố. Hiện tại, người dân đang ở trên $N$ phi thuyền có sức chứa không giới hạn trong thành phố. Tuy nhiên, chính quyền nhận ra rằng chỉ có đủ nhiên liệu cho $K$ phi thuyền bay ra khỏi thành phố.

Vì vậy, chính quyền địa phương lập tức lên kế hoạch gộp người dân từ $N$ phi thuyền vào $K$ phi thuyền để bay ra khỏi thành phố. Chi phí nhiên liệu để di dời khẩn cấp $w_i$ người từ phi thuyền thứ $i$ ở tọa độ $x_i$ sang phi thuyền thứ $j$ ở tọa độ $x_j$ bằng $|x_i-x_j|\times w_i$. Hãy tìm phương án di dời có tổng chi phí nhiên liệu nhỏ nhất.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên $N$ và $K$.
• $N$ dòng tiếp theo, mỗi dòng gồm hai số nguyên $x_i$ và $w_i$: tọa độ của phi thuyền thứ $i$ và số người trên đó.

Dữ liệu ra

In ra chi phí di dời nhỏ nhất.

Ràng buộc

• $1\le N,K\le 5000$
• $1\le x_i,w_i\le {10}^6$

Ví dụ