$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