Две подруги, Алиса и Юки, посадили в своем саду дерево из $$$n$$$ вершин. Дерево — это неориентированный граф без циклов, петель и кратных ребер. Каждое ребро в этом дереве имеет длину $$$k$$$. Изначально вершина $$$1$$$ — корень дерева.

Алиса и Юки выращивают дерево не просто так, они хотят продать его. Стоимостью дерева назовем максимальное расстояние от корня до вершины по всем вершинам дерева. Расстоянием между двумя вершинами $$$u$$$ и $$$v$$$ является сумма длин ребер на пути от $$$u$$$ до $$$v$$$.

Девочки проходили курс юных садоводов, поэтому они умеют модифицировать дерево. За $$$c$$$ монет Алиса и Юки могут поменять корень дерева, выбрав одного из соседей текущего корня и сделав его корнем дерева. Эту операцию можно применять любое количество раз (в том числе и ноль). Обратите внимание, что операция не затрагивает структуру дерева; единственное изменение заключается в том, что корнем дерева становится другая вершина.

Подруги хотят продать дерево с максимальной выгодой. Выгода — это разность стоимости дерева и затрат на все операции.

Помогите девочкам и найдите максимальную выгоду, которую они могут получить, применив к дереву операции произвольное число раз (возможно, ноль).