ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1018. Двоичная яблоня

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Представьте, как должна выглядеть яблоня в двоичном компьютерном мире. Вы правы, она выглядит как двоичное дерево, то есть любая ветка двоичной яблони может ветвиться в точности на две новые ветки. Занумеруем целыми числами корень двоичной яблони, точки ветвления и верхушки верхних ветвей. Пусть корень дерева всегда имеет номер 1, а все числа, используемые при нумерации, лежат в пределах от 1 до N, где N — общее число пронумерованных точек. На рисунке ниже приведён пример нумерации дерева с четырьмя ветвями. N здесь равно 5.
2   5
 \ / 
  3   4
   \ /
    1
Как вы понимаете, не очень удобно собирать яблоки с яблони, у которой много ветвей. Вот почему некоторые ветви следует удалить из дерева. Но вы также заинтересованы в удалении ветвей, которое приведёт к минимальной потере яблок. Известно количество яблок на каждой из ветвей, а также количество ветвей, которые нужно сохранить. Ваша задача — определить, сколько яблок можно оставить на яблоне, удалив лишние ветви.

Исходные данные

В первой строке даны числа N и Q (2 ≤ N ≤ 100; 1 ≤ QN − 1). N обозначает количество пронумерованных точек в дереве, а Q — количество ветвей, которые нужно сохранить. Следующие N − 1 строк содержат описание ветвей. Описание каждой ветви состоит из трёх чисел, разделённых пробелом. Первые два из них определяют конечные точки ветви, третье — число яблок на данной ветви. Вы можете считать, что любая ветвь содержит не более 30000 яблок.

Результат

Выведите единственное число — максимальное количество яблок, которое можно сохранить. Не забудьте сохранить корень яблони ;-)

Пример

исходные данныерезультат
5 2
1 3 1
1 4 10
2 3 20
3 5 20
21
Источник задачи: Ural State University Internal Contest '99 #2