有 $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