Ученые нашли биочип, который при определенных условиях делится на несколько новых биочипов. При этом биочип-родитель прекращает свое существование. Биочипы-потомки обладают каджый своим объемом памяти. Далее биочип можно или использовать (запретив дальнейшее деление), или он будет делиться дальше по заранее известной схеме.
Ученые составили древовидные схемы деления для разных биочипов и точно знают структуру дерева из N элементов, включая объем памяти каждого из потенциальных потомков. Им нужна программа, которая выберет из этого дерева ровно M биочипов, суммарный объем памяти которых максимален. Обратите внимание, что если мы выбираем какой-то биочип, то ни один из его предков или потомков не может быть выбран.
Формат входного файла
В первой строке входного файла находятся два целых числа N и M - количество элементов дерева и количество выбираемых биочипов.
Следующие N строк содержат по два неотрицательных целых числа, разделенных пробелом: номер родителя в дереве и размер собственной памяти a[i]. Каждый биочип идентифицируется числом между 1 и N включительно, строка входного файла с номером i содержит информацию о биочипе с номером i − 1. Ровно один биочип не имеет родителя, в качестве номера его родителя записан 0.
Входные данные таковы, что M биочипов выбрать можно.
Формат выходного файла
Выходной файл должен содержать одно целое число - максимально возможный суммарный объем памяти выбранных M биочипов.
