{"raw_statement":[{"iden":"statement","content":"_Pang_ lives on a tree with $n$ vertices. The vertices are labelled as $1, 2, \\\\dots, n$ and _Pang_ is in vertex $1$. Each vertex has a temperature. On the morning of each day after day 0, the temperature of each vertex decreases by $1$. The temperature doesn't decrease on day 0. On the afternoon of each day, _Pang_ 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 $0$, _Pang_ can cast magic which increases the temperature of the vertex he is in by $k$. For each pair of adjacent vertices $a$ and $b$, _Pang_ can travel from vertex $a$ to vertex $b$ at most once (and from $b$ to $a$ at most once). He can choose not to travel and stay in the current vertex. \n\n_Pang_ wants to cast his magic on each vertex exactly once. He also tries to stay at vertex $1$ as long as possible, before traveling to any other city. Given the temperature of each vertex right before the morning of the day $1$, on which day must _Pang_ prepare for departing? If _Pang_ prepares on day $i$, he can cast his magic on that day and will make his first move on day $i + 1$. If he cannot cast his magic on each vertex exactly once even if he prepares for departing on the day $0$, output $-1$.\n\nThe first line contains two integers $n$ and $k$ ($2 <= n <= 100000, 0 <= k <= 1000000000$).\n\nEach of the next $n -1$ lines contains two integers $x$ and $y$, indicating an edge between vertices $x$ and $y$ ($1 <= x, y <= n$).\n\nThe $(n + 1)$-th line contains $n$ integers $a_1, a_2, \\\\dots, a_n$ — the temperature of vertex $i$ right before the morning of day $1$ ($0 <= a_i <= 1000000000$).\n\nIt's guaranteed that the input is a tree structure.\n\nIf he cannot cast his magic on each vertex exactly once, output $-1$.\n\nOtherwise, output a single integer $x$ — he must prepare for departing from vertex $1$ on day $x$. Day $1$ is the day after day $0$, and so on.\n\n"},{"iden":"input","content":"The first line contains two integers $n$ and $k$ ($2 <= n <= 100000, 0 <= k <= 1000000000$).Each of the next $n -1$ lines contains two integers $x$ and $y$, indicating an edge between vertices $x$ and $y$ ($1 <= x, y <= n$).The $(n + 1)$-th line contains $n$ integers $a_1, a_2, \\\\dots, a_n$ — the temperature of vertex $i$ right before the morning of day $1$ ($0 <= a_i <= 1000000000$).It's guaranteed that the input is a tree structure."},{"iden":"output","content":"If he cannot cast his magic on each vertex exactly once, output $-1$.Otherwise, output a single integer $x$ — he must prepare for departing from vertex $1$ on day $x$. Day $1$ is the day after day $0$, and so on."},{"iden":"examples","content":"Input3 1\n1 2\n1 3\n4 3 5\nOutput1\nInput3 1\n1 2\n1 3\n2 10 10\nOutput-1\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ k \\in \\mathbb{Z}_{\\geq 0} $.  \nLet $ T = (V, E) $ be a tree with $ V = \\{1, 2, \\dots, n\\} $, $ |V| = n $, and $ 1 \\in V $ is the root.  \nLet $ a_i \\in \\mathbb{Z}_{\\geq 0} $ denote the initial temperature of vertex $ i $ just before morning of day 1.  \n\n**State Dynamics**  \nLet $ t_d(v) $ be the temperature of vertex $ v $ at the start of day $ d $ (before morning decrement).  \n- $ t_1(v) = a_v $  \n- For $ d \\geq 1 $, before morning of day $ d+1 $: $ t_{d+1}(v) = t_d(v) - 1 $  \n- On afternoon of day $ d $, Pang may move from $ u $ to $ v $ if $ t_d(u) > 0 $ and $ t_d(v) \\geq 0 $, and the edge $ (u,v) $ has not been traversed in either direction.  \n- On evening of day $ d $, if $ t_d(v) \\geq 0 $ and Pang is at $ v $, he may cast magic: $ t_d(v) \\leftarrow t_d(v) + k $, **exactly once per vertex**.  \n\n**Constraints**  \n1. Each vertex must be visited and magic cast **exactly once**.  \n2. Each edge may be traversed **at most once in each direction**.  \n3. Pang starts at vertex 1 on day 1 (before any action).  \n4. He must delay departure (first move) as long as possible.  \n5. Preparation day $ x $: magic can be cast on day $ x $, first move occurs on day $ x+1 $.  \n\n**Objective**  \nFind the minimal day $ x \\in \\mathbb{Z}_{\\geq 0} $ such that:  \n- Pang can cast magic on all $ n $ vertices exactly once, following movement and temperature constraints,  \n- He remains at vertex 1 until day $ x $ (i.e., no move before day $ x+1 $),  \n- If no such $ x $ exists, output $ -1 $.  \n\n**Note**: Casting magic on vertex $ v $ requires $ t_d(v) \\geq 0 $ at the evening of day $ d $, and the vertex must be visited on day $ d $.","simple_statement":"Pang starts at vertex 1 on a tree with n vertices. Each vertex has a temperature. Every morning (except day 0), all temperatures drop by 1. Each afternoon, Pang can move to an adjacent vertex only if his current vertex has positive temperature and the target has non-negative temperature. Each evening, if he’s on a vertex with temperature >= 0, he can cast magic to increase its temperature by k — but he must cast magic on each vertex exactly once. He wants to delay leaving vertex 1 as long as possible. Find the earliest day he must start preparing (so he can cast magic on all vertices exactly once). If impossible, output -1.","has_page_source":false}