Descripción

Sashka es responsable del mantenimiento de las flores en el jardín de la ciudad. El jardín consiste en ~N~ macetas enumeradas desde ~1~ hasta ~N~, donde algunas macetas están conectadas por tuberías. Las macetas y las tuberías forman un grafo no dirigido, conexo y acíclico; en este, las macetas serían los vértices y las tuberías serían las aristas. Cada maceta contiene una bomba de agua que puede proporcionar agua a la macera desde el subsuelo. El agua riega a la maceta en el que la bomba está ubicada y también a algunas otras macetas que se conecten a la inicial por una serie de tuberías. Las bombas están enumeradas desde ~1~ hasta ~N~ y el número asociado a cada bomba coincide con el número asociado a la maceta donde la bomba se ubica. Si una bomba localizada en la maceta número (~1 \le x \le N~) y funciona por minutos, el agua llegará a todas las macetas que tengan una distancia dentro del rango ~p~ - ~1~ de aristas desde la maceta en el grafo. En el sistema de bombas una bomba funciona primero, luego otra y así continúa. Es decir, nunca dos bombas funcionan al mismo tiempo.

Una bomba puede funcionar más de una vez. Una maceta se considera regada si el agua llega a ella independientemente de la bomba de procedencia. Para evitar un mal funcionamiento, la bomba ~m~ debe funcionar a lo más por ~t_m~ minutos. El tiempo de funcionamiento de una bomba debe ser un número entero. Todas las bombas consumen electricidad de forma idéntica: ~1~ minuto de funcionamiento cuesta ~c_1~ euros, ~2~ minutos de funcionamiento cuestan ~c_2~ euros y así sucesivamente. Si una bomba no está en funcionamiento no consume electricidad.

Tarea

A Sashka se le asigna la tarea de determinar la cantidad mínima de dinero para la electricidad, cuando funciona un conjunto apropiado de bombas, para que todas las macetas de flores puedan ser regadas. Escribe un programa, que resuelve la tarea de Sashka.

Entrada

La primera línea de la entrada estándar contiene un entero ~N~, igual al número de macetas (y bombas) en el jardín.

La segunda línea contiene ~N~ enteros no negativos ~c_1~, ~c_2~, ..., ~c_N~, separados por espacios – el dinero gastado en electricidad que una bomba consume por ~1, 2, ..., N~ minutos de funcionamiento respectivamente.

La tercera línea contiene ~N~ enteros no negativos ~t_1, t_2, ..., t_N~, separados por espacios – el tiempo máximo de funcionamiento por cada bomba. Si alguno de estos tiempos es ~0~, esto significa que la bomba no puede ser usada.

Las últimas ~N - 1~ líneas contienen dos enteros positivos ~u~ y ~v~, que definen una tubería (arista) que conecta las macetas numero ~u~ y ~v~. Se garantiza que las macetas y las tuberías forman un grafo conexo y acíclico.

Salida

En la única línea de la salida estándar, el programa debe imprimir la mínima cantidad de dinero para la electricidad tal que todas las macetas sean regadas. Si es imposible regarlas todas, imprimir. ~-1~.

Restricciones

• ~1 \le N \le 2 000~
• ~0 \le c_i \le 10^6~
• ~0 \le t_i \le N~

Subtareas

Limites Puntos

No | N | Otros | Subtareas requeridas | puntos

1 | - | El caso ejemplo | - | 0 puntos

2 | N ≤ 8 | - | 1 | 11 puntos

3 | N ≤ 75 | El grafo es una cadena | - | 12 puntos

4 | N ≤ 500 | El grafo es una cadena | 3 | 11 puntos

5 | N ≤ 2 000 | El grafo es una cadena | 3 - 4 | 13 puntos

6 | N ≤ 75 | - 1 | - 3 | 17 puntos

7 | N ≤ 500 | - | 1 - 4; 6 | 14 puntos

8 | N ≤ 2 000 | - | 1 - 7 | 22 puntos

El puntaje de una subtarea solo se gana si se resuelven todos los casos para ella.

• Un grafo es una cadena si todos los vértices tienen grado a lo más ~2~ y hay exactamente ~2~ de ellos que tienen grado ~1~.

Ejemplo de Entrada #1

1 4 9 16 25 36 49 64
1 5 1 1 0 0 5 0
1 2
2 3
1 4
2 5
2 6
4 7
7 8

Ejemplo de Salida #1

8

Ejemplo de Entrada #2

7
1 4 9 16 25 36 49
0 5 5 0 0 0 0
1 2
2 4
1 3
1 5
3 7
3 6

Ejemplo de Salida #2

13

Explicación del ejemplo #1

El costo minimo se logra cuando la bomba ~No 2~ funciona por ~2~ minutos y la bomba ~No 7~ funciona por ~2~ minutos. La electricidad consumida es ~c_2~ + ~c_2~ = ~4~ + ~4~ = ~8~ euros.

Explicación del ejemplo #2

El costo minimo se logra cuando la bomba ~No 3~ funciona por ~3~ minutos y la bomba ~No 2~ funciona por ~2~ minutos. La electricidad consumida es ~c_2~ + ~c_3~ = ~4~ + ~9~ = ~13~ euros.