La red de televisión de los azucareros del centro se planea transmitir un importante encuentro de beisbol. Su red de transmisores y usuarios puede representarse como un árbol. La raíz del árbol es un transmisor que emite el partido de beisbol, las hojas del árbol son los usuarios potenciales y los otros vértices en el árbol son los transmisores.

El precio de transmisión de una señal de un transmisor a otro o al usuario es dado. El precio de la transmisión entera es la suma de precios de todas las transmisiones de las señales individuales. Cada usuario tiene la intención de pagar una cierta cantidad de dinero para ver el partido y la red de TV entonces decide o no proveer la señal al usuario.

Escriba un programa que encuentre el número máximo de usuarios capaces de ver el partido tal que la red de TV no pierda dinero por la trasmisión del partido.

Entrada

La primera línea de la entrada contiene dos enteros ~N~ y ~M~, , el número de vértices en el árbol y el número de usuarios potenciales. La raíz del árbol está marcada con el número 1, mientras los otros transmisores están numerados de ~2~ a ~N-M~ y los usuarios potenciales están numerados de ~N-M+1~ a ~N~. Las siguientes ~N-M~ líneas contienen datos acerca de los trasmisores en siguiente la forma:

~K~ ~A_1~ ~C_1~ ~A_2~ ~C_2~ ~...~ ~A_K~ ~C_K~

Significa que un transmisor transmite la señal a ~K~ transmisores o usuarios, cada uno de ellos descrito por el par de números ~A~ y ~C~, número del usuario y el costo de transmisión de la señal a ellos. La última línea contiene los datos acerca de los usuarios, contiene ~M~ enteros representando respectivamente el precio que cada uno de ellos están dispuesto a pagar por ver el partido.

Salida

La primera y única línea de la salida debe contener el número máximo de usuarios descrito en el texto de arriba.

Restricciones

• ~2 \leq N \leq 3000~.
• ~1 \leq M \leq N-1~.

Ejemplo #1 de Entrada

5 3
2 2 2 5 3
2 3 2 4 3
3 4 2

Ejemplo #1 de Salida

2

Ejemplo #2 de Entrada

5 3
2 2 2 5 3
2 3 2 4 3
4 4 2

Ejemplo #2 de Salida

3

Ejemplo #3 de Entrada

9 6
3 2 2 3 2 9 3
2 4 2 5 2
3 6 2 7 2 8 2
4 3 3 3 1 1

Ejemplo #3 de Salida

5