Компьютерная сеть в некотором доме строилась по принципу присоединения нового компьютера к последнему из уже подключенных. Никакие два компьютера, будучи подключенными в сеть, между собой дополнительно никак не связывались. Таким образом, в сеть были объединены последовательно n компьютеров. Соседи обменивались информацией между собой, но в какой-то момент поняли, что им нужны прокси-серверы. Компьютерное сообщество дома решило установить прокси-серверы ровно на k компьютеров. Осталось только решить, какие именно компьютеры выбрать для этой цели. Главным критерием является ежемесячная стоимость обслуживания серверами всех компьютеров.
Для каждого компьютера установлен тариф его обслуживания, выраженный в рублях за метр провода. Стоимость обслуживания одного компьютера каким-то сервером равна тарифу компьютера, умноженному на суммарную длину провода от этого компьютера до сервера, которым он обслуживается.
Ваша задача написать программу, которая выберет такие k компьютеров, чтобы установить на них прокси-серверы, что общие затраты на обслуживание всех компьютеров были бы минимальными.
В первой строке записано два целых числа n и k - количество компьютеров в сети и количество прокси-серверов, которые нужно установить (1 ≤ k ≤ n ≤ 2000).
Все компьютеры в сети пронумерованы числами от 1 до n по порядку подключения.
Во второй строке записано одно целое число t_{i }- тариф обслуживания первого компьютера.
В следующих n – 1 строках записано через пробел по два целых неотрицательных числа l_i, t_{i }- информация об остальных компьютерах в сети по порядку номеров. l_{i }- длина провода, соединяющего i-й компьютер с соседним с меньшим номером, t_{i }- тариф обслуживания данного компьютера (2 ≤ i ≤ n). Все l_{i }и t_{i }не превышают 10^6.
В первой строке вывести минимальную стоимость обслуживания всех компьютеров всеми серверами. Во второй строке должны быть записаны через пробел k номеров компьютеров, на которые необходимо установить серверы. При существовании нескольких вариантов размещения разрешается вывести любой.