El maestro ha dibujado un árbol de $N$ vértices en la pizarra. Por desgracia, se niega a borrarlo hasta que cada arista esté orientada. Nadie sabe por qué, pero el maestrito lo llama «investigación importante».

Cada vértice $v$ tiene dos valores, $k_v$ y $w_v$. Después de orientar todas las aristas, el maestro otorga $w_v$ puntos al vértice $v$ si su grado de salida es exactamente $k_v$:

$$\operatorname{outdeg}(v) = k_v$$

En caso contrario, el vértice obtiene $0$ puntos y recibe una mirada de decepción del maestro.

Orienta todas las aristas para maximizar la suma total de puntos y, más importante aún, mantener feliz al maestro.

La primera línea contiene un entero $N$, el número de vértices del árbol.

La segunda línea contiene $N$ enteros:

La tercera línea contiene $N$ enteros:

Cada una de las siguientes $N - 1$ líneas contiene dos enteros $u$ y $v$, que indican una arista entre los vértices $u$ y $v$.

Restricciones

• $1 \le N \le 2 \cdot 10^5$
• $0 \le k_v \le \deg(v)$
• $1 \le w_v \le 10^9$
• El grafo dado es un árbol.

Imprime un único entero: la máxima suma de puntos que puede obtenerse orientando todas las aristas.

Explicación

En el primer ejemplo, el único vértice tiene grado de salida 0, por lo que aporta 7 puntos.

En el segundo ejemplo, al orientar la arista como $1 \to 2$, ambos vértices alcanzan sus grados de salida requeridos y aportan un total de $5 + 8 = 13$ puntos.

En el tercer ejemplo, se orientan las aristas como $1 \to 2$ y $2 \to 3$. Los vértices 2 y 3 alcanzan sus grados de salida requeridos y aportan $10 + 7 = 17$ puntos.