Mashmokh is playing a new game. In the beginning he has k liters of water and p coins. Additionally he has a rooted tree (an undirected connected acyclic graph) that consists of m vertices. Each vertex of the tree contains a water tank that is empty in the beginning.

The game begins with the fact that Mashmokh chooses some (no more than k) of these tanks (except the root) and pours into each of them exactly 1 liter of water. Then the following process is performed until there is no water remained in tanks.

• The process consists of several steps.
• At the beginning of each step Mashmokh opens doors of all tanks. Then Mashmokh closes doors of some tanks (he is not allowed to close door of tank in the root) for the duration of this move. Let's denote the number of liters in some tank with closed door as w, Mashmokh pays w coins for the closing of that tank during this move.
• Let's denote by x₁,x₂,...,x_m as the list of vertices of the tree sorted (nondecreasing) by their depth. The vertices from this list should be considered one by one in the order. Firstly vertex x₁ (which is the root itself) is emptied. Then for each vertex x_i (i>1), if its door is closed then skip the vertex else move all the water from the tank of vertex x_i to the tank of its father (even if the tank of the father is closed).

Suppose l moves were made until the tree became empty. Let's denote the amount of water inside the tank of the root after the i-th move by w_i then Mashmokh will win max(w₁,w₂,...,w_l) dollars. Mashmokh wanted to know what is the maximum amount of dollars he can win by playing the above game. He asked you to find this value for him.