$n$마리의 개구리가 다과회에 초대되었다. 편의상 개구리에는 $1, 2, \dots, n$의 번호가 붙어 있다.

다과회에서는 홍차와 녹차를 제공한다. 개구리마다 선호하는 차가 있다. 홍차만 마시거나, 녹차만 마시거나, 둘 다 마실 수 있다.

서로 싫어하는 개구리 쌍이 $m$개 있다. 이들에게 같은 종류의 차를 제공하면 싸운다.

다행히 개구리를 $2$개의 그룹으로 나누어 같은 그룹의 어떤 두 개구리도 서로 싫어하지 않도록 할 수 있다.

개구리는 보석을 좋아한다. $i$번째 개구리에게 차 대신 $w_i$개의 보석을 지급하면, 그 개구리는 더 이상 다른 개구리와 싸우지 않는다.

파티 관리자는 싸움이 일어나지 않도록 차를 제공하거나 보석을 지급하는 방법을 정해야 하며, 지급하는 보석의 총개수를 최소화해야 한다.

입력

입력은 여러 테스트로 구성된다. 각 테스트에 대해:

첫 번째 줄에는 $2$개의 정수 $n, m$이 주어진다 ($1 \leq n \leq 10^3, 0 \leq m \leq 10^4$). 두 번째 줄에는 $n$개의 정수 $w_1, w_2, \dots, w_n$이 주어진다. ($1 \leq w_i \leq 10^6$).

세 번째 줄에는 $n$개의 정수 $p_1, p_2, \dots, p_n$이 주어진다. ($1 \leq p_i \leq 3$). $p_i = 1$이면 $i$번째 개구리는 홍차만 마신다. $p_i = 2$이면 녹차만 마시며, $p_i = 3$이면 둘 다 마실 수 있다.

다음 $m$개의 줄에는 각각 $2$개의 정수 $a_i, b_i$가 주어지며, 개구리 $a_i$와 $b_i$가 서로 싫어한다는 뜻이다. ($1 \leq a_i, b_i \leq n$)

출력

각 테스트에 대해 지급해야 하는 보석의 최소 총개수를 나타내는 정수 $1$개를 출력한다.

예제

입력 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

출력 1

0
1
1