Se invita a $n$ ranas a una merienda. Por comodidad, las ranas están numeradas del $1, 2, \dots, n$.

En la merienda se sirven té negro y té verde. Cada rana tiene sus propias preferencias. Puede beber únicamente té negro, únicamente té verde o aceptar ambos.

Hay $m$ parejas de ranas que se desagradan mutuamente. Pelean cuando se les sirve el mismo tipo de té.

Por suerte, las ranas se pueden dividir en $2$ grupos de modo que ninguna pareja de ranas del mismo grupo se desagrade mutuamente.

A las ranas les gustan las gemas. Si a la rana $i$ se le pagan $w_i$ gemas en lugar de servirle té, ya no peleará con las demás.

El encargado de la fiesta debe decidir cómo servir el té o pagar gemas para evitar las peleas, minimizando el número total de gemas pagadas.

Entrada

La entrada consta de varias pruebas. Para cada prueba:

La primera línea contiene $2$ enteros $n, m$ ($1 \leq n \leq 10^3, 0 \leq m \leq 10^4$). La segunda línea contiene $n$ enteros $w_1, w_2, \dots, w_n$. ($1 \leq w_i \leq 10^6$).

La tercera línea contiene $n$ enteros $p_1, p_2, \dots, p_n$. ($1 \leq p_i \leq 3$). $p_i = 1$ significa que la rana $i$ solo bebe té negro. $p_i = 2$ significa que solo bebe té verde, mientras que $p_i = 3$ significa que acepta ambos.

Cada una de las siguientes $m$ líneas contiene $2$ enteros $a_i, b_i$, que indican que las ranas $a_i$ y $b_i$ se desagradan mutuamente. ($1 \leq a_i, b_i \leq n$)

Salida

Para cada prueba, escribe $1$ entero que indique el número mínimo total de gemas pagadas.

Ejemplos

Entrada 1

2 1
1 1
3 3
1 2
2 1
1 1
2 2
1 2
3 2
2 1 2
1 3 2
1 2
2 3

Salida 1

0
1
1