Машмох играет в новую игру. В начале у него есть k литров воды и p монеток. Также у него есть корневое дерево (неориентированный связный ациклический граф), состоящее из m вершин. Каждая вершина дерева содержит резервуар с водой, изначально пустой.

Игра начинается с того, что Машмох выбирает несколько (не более k) таких резервуаров (кроме того, что находится в корне) и льет в каждый ровно 1 литр воды. Затем следующий процесс продолжается, пока в резервуарах не остается воды.

• Процесс состоит из нескольких итераций.
• В начале каждой итерации Машмох открывает крышки всех резервуаров. Затем он закрывает крышки некоторых резервуаров (ему нельзя закрывать крышку корневого резервуара) на время этой итерации. Пусть некоторый резервуар содержал w литров воды и был закрыт на данной итерации, тогда Машмох платит w монеток за закрытие этого резервуара.
• Обозначим через x₁, x₂, ..., x_m список вершин дерева, отсортированный в порядке неубывания по глубине. Будем рассматривать вершины из этого списка одну за одной. Сперва опустошается резервуар в вершине x₁ (то есть, корень). Затем для каждой вершины x_i (i > 1), если ее резервуар закрыт, вершина пропускается, иначе вся вода переливается из резервуара вершины x_i в резервуар ее родителя (несмотря на то, что резервуар родителя может быть закрытым).

Предположим, что до опустошения всех резервуаров дерева произошло l итераций. Обозначим количество воды в резервуаре корня после i-й итерации как w_i. В результате описанного процесса Машмох выиграет max(w₁, w₂, ..., w_l) долларов. Машмох хочет знать, какое максимальное количество долларов он может выиграть, сыграв приведенную выше игру. Он просит вас найти для него это значение.