lives on a tree with vertices. The vertices are labelled as and is in vertex . Each vertex has a temperature. On the morning of each day after day 0, the temperature of each vertex decreases by . The temperature doesn't decrease on day 0. On the afternoon of each day, can travel to an adjacent vertex, provided that he is at a vertex with positive temperature and his destination vertex has a non-negative temperature. On the evening of each day, if the temperature is higher than or equal to , can cast magic which increases the temperature of the vertex he is in by . For each pair of adjacent vertices and , can travel from vertex to vertex at most once (and from to at most once). He can choose not to travel and stay in the current vertex.

wants to cast his magic on each vertex exactly once. He also tries to stay at vertex as long as possible, before traveling to any other city. Given the temperature of each vertex right before the morning of the day , on which day must prepare for departing? If prepares on day , he can cast his magic on that day and will make his first move on day . If he cannot cast his magic on each vertex exactly once even if he prepares for departing on the day , output .