Descripción

Finalmente el mundo de las criptomonedas, en las que estuviste mucho tiempo invirtiendo, dieron sus frutos y eres multimillonario. Lo primero que compras es una máquina del tiempo (sí, en 2046 ya existen) para ver quiénes serán tus descendientes a los que heredarás tu fortuna. Luego de innumerables viajes en el tiempo, has podido recolectar la información en forma de un árbol de \(N\) nodos, numerados del \(1\) al \(N\), siendo tú el nodo \(1\). Cada nivel del árbol representa las generaciones que habrá en tu familia (el primer nivel son tus hijos, el segundo nivel son tus nietos, el tercer nivel son tus bisnietos, etc).

Una vez teniendo esta información lo que quisieras hacer es dejarle una herencia a al menos \(K\) de tus descendientes, pero lo que pondrás en tu testamento no será dinero (porque eso sería regalarles la vida), sino libros!!!!

Problema

Actualmente tienes \(X\) libros para heredar, afortunadamente también recolectaste la información de cuántos libros van a ocupar tus descendientes en toda su vida, por lo que deseas conocer cuál será la primera generación en la que podrás cumplir tu deseo de heredarle a al menos \(K\) de tus descendientes todos los libros que ocuparán en su vida.

Entrada

La primera línea contiene tres enteros: \(N, X, K\). Denotando la cantidad de nodos en el árbol, la cantidad de libros que tienes y la cantidad de descendientes a los que quieres heredar, respectivamente.

En la segunda línea habrá \(N\) enteros: \(N_1, N_2, N_3, ..., N_i\). Que representan la cantidad de libros que cada descendiente \(i\) ocupará en su vida. Para \(i = 1\) la cantidad será \(0\) (porque eres tú).

En las siguientes \(N - 1\) líneas habrá dos enteros: \(a_i, b_i\). Que indican que el nodo \(a_i\) es el padre del nodo \(b_i\).

Salida

Un único entero \(G\) que indica la primera generación en la que podrás heredar a al menos \(K\) descendientes. En caso de que esto no sea posible con ninguna generación, imprime \(-1\).

Ejemplos

Entrada

4 10 1
0 3 20 1
1 2
1 3
1 4

Salida

1

Explicación: Solo necesitas heredar a uno de tus descendientes, por lo que basta con heredar a cualquiera de tus hijos (menos el que tiene índice \(3\)).

Entrada

5 10 2
0 1 1 1 1
1 2
2 3
3 4
4 5

Salida

2

Explicación: Como solo tienes un hijo, necesitas heredarle también a tu nieto para cumplir tu requisito de \(K = 2\).

Límites

• \(1 \leq N \leq 10^6\).
• \(1 \leq X \leq 10^{15}\).
• \(1 \leq K \leq 10^6\).
• \(1 \leq N_i \leq 10^9\).