Упорядочивание Куч
Горнодобывающая компания добывает тербий, редкий металл, используемый для создания легких магнитов, из речного песка. Они ведут добычу в 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 куч.