%server       - Всесибирская олимпиада, очный тур (29 ноября 2009)

\begin{problem}{Сервера}{server.in}{server.out}{0.5 c}{256 Мб}

\begin{flushright}
{\it Спонсор этой задачи~--- всесибирская олимпиада 2009. Новосибирск -- город мечты!}
\end{flushright}

Компьютерная сеть в некотором доме строилась по принципу присоединения нового компьютера к последнему из уже подключенных. Никакие два компьютера, будучи подключенными в сеть, между собой дополнительно никак не связывались. Таким образом, в сеть были объединены последовательно $N$ компьютеров. Соседи обменивались информацией между собой, но в какой-то момент поняли, что им нужны прокси-серверы. Компьютерное сообщество дома решило установить прокси-серверы ровно на $K$ компьютеров. Осталось только решить, какие именно компьютеры выбрать для этой цели. Главным критерием является ежемесячная стоимость обслуживания серверами всех компьютеров.

Для каждого компьютера установлен тариф его обслуживания, выраженный в рублях за метр провода. Стоимость обслуживания одного компьютера каким-то сервером равна тарифу компьютера, умноженному на суммарную длину провода от этого компьютера до сервера, которым он обслуживается.

Ваша задача написать программу, которая выберет такие $K$ компьютеров, чтобы установить на них прокси-серверы, что общие затраты на обслуживание всех компьютеров были бы минимальными

\InputFile

В первой строке входного файла записано два целых числа $N$ и $K$ --- количество компьютеров в сети и количество прокси-серверов, которые нужно установить ($1 \leq K \leq N \leq 2000$).

Все компьютеры в сети пронумерованы числами от 1 до $N$ по порядку подключения.

Во второй строке записано одно целое число $T_1$ — тариф обслуживания первого компьютера.

В следующих $N$ – 1 строках записано через пробел по два целых неотрицательных числа $L_i$, $T_i$ --- информация об остальных компьютерах в сети по порядку номеров. $L_i$ --- длина провода, соединяющего $i-ый$ компьютер с соседним с меньшим номером, $T_i$ --- тариф обслуживания данного компьютера ($2 \leq i \leq N$). Все $L_i$ и $T_i$ от $0$ до $10^6$. 

\OutputFile

В первую строку выходного файла необходимо вывести одно целое число --- минимальную стоимость обслуживания всех компьютеров всеми серверами. Во второй строке должны быть записаны через пробел $K$ номеров компьютеров, на которые необходимо установить серверы. При существовании нескольких вариантов размещения разрешается вывести любой.

\Example

\begin{example}
\exmp{3 1
10
2 2
3 3
}{
19
1
}%
\exmp{3 2
10
2 2
3 3
}{4
1 3
}%
\end{example}

\end{problem}
