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