Розташування Куп
Компанія з видобутку корисних копалин видобуває тербій, рідкісний метал, що використовується для виготовлення легких магнітів, з річкового піску. Вони здійснюють видобуток у N точках на річці Лонг, кожна з яких визначається відстанню від витоку річки. У кожній точці видобутку з річки видобувається відносно невелика, але дуже цінна купа мінеральної руди.
Для збору мінеральної руди компанія перегруповує N видобутих куп у меншу кількість K куп, причому кожна нова купа розташовується в одній з початкових точок видобутку. Потім ці новоутворені купи збираються вантажівками.
Для перегрупування N куп використовується баржа, яка може перевозити будь-яку кількість мінеральної руди завдяки своїм великим розмірам. Баржа починає рух від витоку річки і може рухатися тільки вниз за течією, тому купу, видобуту в точці X, можна перевезти в точку Y лише якщо Y > X. Кожна купа повністю переміщується в іншу точку видобутку або не переміщується взагалі. Вартість переміщення купи вагою W з точки X в точку Y дорівнює W×(Y-X). Загальна вартість перегрупування є сумою витрат на переміщення кожної купи. Зверніть увагу, що купа, яка не переміщується, не впливає на загальну вартість.
З огляду на значення N і K, точки видобутку N та вагу купи, яку виробила кожна точка видобутку, напишіть програму, яка обчислює мінімальну загальну вартість перегрупування N початкових куп у K куп.
Вхідні дані
Кожен тестовий випадок описується кількома рядками. Перший рядок містить два цілі числа N і K, що позначають відповідно кількість початкових куп і бажану кількість куп після перегрупування (1 ≤ K < N ≤ 1000). Кожен з наступних N рядків описує одну з початкових куп двома цілими числами X і W, що вказують, що точка видобутку X виробила купу вагою W (1 ≤ X, W ≤ 10^6). У межах кожного тестового випадку купи подані в строго зростаючому порядку з урахуванням їх точок видобутку.
Вихідні дані
Для кожного тестового випадку виведіть рядок з цілим числом, що представляє мінімальну загальну вартість перегрупування N початкових куп у K куп.