問題文

$N$ 頂点 $M$ 辺の単純連結無向グラフがあります。 $i\ (1\le i \le M)$ 番目の辺は頂点 $u_i,\ v_i$ を結びます。

$N$ 個の頂点ははじめ、色が塗られていません。chinerist 君はこれから以下のようにして各頂点を赤色、または青色で塗ることにしました。

まずはじめに好きな頂点を選び、頂点を赤色、青色のうち好きな方で塗り、駒を置きます。

つぎに以下のような操作を $0$ 回以上行います。

• 現在駒が置かれている頂点を $i$ とする。頂点 $i$ と辺で結ばれているような頂点 $j$ を $1$ つ選ぶ。頂点 $j$ を赤色、青色のうち、頂点 $i$ の色とは異なる色で塗り（すでに色が塗られている場合は上書きする）、駒を頂点 $j$ に移動する。

操作を終えた後、各頂点 $i\ (1 \le i \le N)$ について、赤色が塗られていた場合 $R_i$ 点、青色が塗られていた場合 $B_i$ 点、色が塗られていない場合は $0$ 点を得ることができます。

chinerist 君が適切に操作を行った場合、操作を終えた後最大で何点得られるか求めてください。

入力

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$
$R_1$ $R_2$ $\dots$ $R_N$
$B_1$ $B_2$ $\dots$ $B_N$

• $2 \le N \le 1000$
• $N-1 \le M \le \min(\frac{N(N-1)}{2},1000)$
• $1 \le u_i < v_i \le N$
• $1 \le R_i,\ B_i \le 10^9$
• 与えられる入力はすべて整数
• 与えられるグラフは単純連結無向グラフ

出力

答えを出力してください。

最後に改行してください。

サンプル

3 3
1 2
2 3
1 3
1 2 3
4 3 5

11

15 20
2 14
1 12
10 11
9 12
4 12
3 8
7 11
1 2
11 14
7 9
14 15
2 6
6 10
3 4
10 13
9 15
5 15
5 8
5 13
3 6
77 109 121 121 163 117 125 149 82 136 81 130 125 102 106
166 39 46 43 69 63 51 57 5 38 14 33 71 29 35

1712