Монокарп играет в компьютерную игру, в которой он управляет империей. Империя состоит из \(n\) городов, соединенных \(n - 1\) дорогой. Города пронумерованы от \(1\) до \(n\). Из каждого города можно добраться до любого другого по дорогам.
Поездка по одной дороге занимает \(2\) часа. Однако, это можно улучшить. Монокарп может построить вокзалы в не более чем \(k\) городах. После того, как они построены, все существующие дороги, которые соединяют два города с вокзалами, превращаются в железные дороги, поездка по которым занимает \(1\) час.
Пусть \(f(x, y)\) будет суммарным временем, которое потребуется, чтобы проехать по дорогам на кратчайшем пути между городами \(x\) и \(y\).
Монокарп хочет построить не более \(k\) вокзалов таким образом, чтобы минимизировать следующее значение: \(\sum \limits_{v=1}^{n} \sum \limits_{u=1}^{v-1} f(v, u)\) (суммарное время, необходимое, чтобы добраться из каждого города до каждого другого города). Какое наименьшее значение он может получить?
Выходные данные
На каждый набор входных данных выведите одно целое число — наименьшее суммарное время, необходимое, чтобы добраться из каждого города до каждого другого города, которое Монокарп может получить, если построит не более \(k\) вокзалов.