Гусеница решила побывать в каждой вершине дерева. Изначально она сидит в корне.
Дерево представлено как корневое дерево с корнем в вершине \(1\). Каждое переползание в соседнюю вершину у неё занимает \(1\) минуту.
А под деревом стоит батут. Если гусеница отцепится от дерева и упадёт на батут, то за \(0\) секунд окажется в корне дерева. Но батут старый и выдержит не более \(k\) падений гусеницы.
За какое минимальное время гусеница сможет обойти дерево?
Более формально — надо найти минимальное время, нужное, чтобы посетить все вершины дерева, если гусеница начинает в корне (вершине \(1\)) и двигается с помощью двух способов.
- Перейти по ребру в одну из соседних вершин: тратит \(1\) минуту.
- Телепортироваться в корень: не тратит времени, никакие новые вершины не становятся посещёнными.
Второй способ (телепортацию) можно применить не более \(k\) раз. Гусеница может закончить путешествие в любой вершине.
Выходные данные
В единственной строке выведите одно число — минимальное число минут, за которое можно побывать во всех вершинах дерева.
Примечание
На картинке показан один из способов обойти дерево из первого теста за 9 минут.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8 1
1 1 2 2 4 3 3
|
9
|
|
2
|
4 0
4 4 1
|
4
|