El Granjero Juan está reuniendo a las vacas. Su granja contiene una red de ~N~ ~(1 \leq N \leq 100,000)~ campos convenientemente numerados ~1..N~ y conectados por ~N-1~ caminos unidreccionales que eventualmente llevan al campo 1. Los caminos y campos forman un árbol.

Cada campo ~i > 1~ tiene un solo camino de salida de un solo sentido al campo ~P_i~, y contiene actualmente ~C_i~ vacas ~(1 \leq C_i \leq 1,000,000,000)~. En cada unidad de tiempo, no más de ~M_i~ ~(0 \leq M_i \leq 1,000,000,000)~ vacas pueden ir del campo i al campo ~P_i~ ~(1 \leq P_i \leq N)~ (esto es solamente ~M_i~ vacas pueden recorrer el camino).

El Granjero Juan quiere que todas las vacas se congreguen en el campo ~1~ (el cual no tiene límite en el número de vacas que puede tener). Las reglas son como siguen:

• Se considera que el tiempo tiene unidades discretas.
• Cualquier vaca dada puede recorrer caminos múltiples en la misma unidad de tiempo. Sin embargo, no más de ~M_i~ vacas en total pueden dejar el campo ~i~ (esto es, recorrer su camino de salida) en la misma unidad de tiempo.
• Las vacas nunca abandonan el campo #1.

En otras palabras, en cada paso de tiempo, cada vaca tiene la posibilidad o de a) Permanecer en su campo actual. b) Moverse a través de uno o más campos hacia el campo #1, en tanto no se violen las restricciones de cuello de botella para cada camino.

El Granjero Juan quiere saber cuántas vacas pueden llegar al campo 1 en ciertos tiempos. En particular él tiene una lista de ~K~ ~(1 \leq K \leq 10,000)~ tiempos ~T_i~ ~(1 \leq T_i \leq 1,000,000,000)~, y quiere saber para cada ~T_i~ en la lista, el número máximo de vacas que pueden llegar al pastizal 1 en ~T_i~ si se organiza el desplazamiento de vacas para optimizar esta cantidad.

Considere un ejemplo donde el árbol es una línea recta, y la lista ~T_i~ contiene únicamente ~T_1 = 5~, y las vacas están distribuidas como se muestra:

Locn:      1---2---3---4      <-- números ID de los campos
C_i:       0   1   12  12     <-- número actual de las vacas
M_i:           5   8   3      <-- Limites para el recorrido de caminos, el campo 1 no tiene limite pues no tiene salida

La solución es como sigue: el objetivo es mover vacas al campo 1:

Arbol:     1---2---3---4
t=0        0   1   12  12     <-- estado inicial
t=1        5   4   7   9      <-- el campo 1 tiene vacas de los campos 2 
t=2        10  7   2   6          y 3
t=3        15  7   0   3
t=4        20  5   0   0
t=5        25  0   0   0

Por lo tanto, la respuesta es 25: todas las 25 vacas pueden llegar al campo 1 en tiempo t=5.

Entrada

• Línea 1: Dos enteros separados por espacio: ~N~ y ~K~
• Líneas 2..N: La línea i (no i+1) describe el campo i con tres enteros separados por espacio: ~P_i~; ~C_i~ y ~M_i~
• Líneas N+1..N+K: La línea ~N+i~ contiene un solo entero: ~T_i~

Salida

Líneas 1..K: La línea ~i~ contiene un solo entero que es el número máximo de vacas que pueden llegar al campo 1 en el tiempo ~T_i~.

Ejemplo de Entrada

4 1
1 1 5
2 12 7
3 12 3
5

Ejemplo de Salida

25

USACO JAN11 Gold Problem 'bottleneck'