問題文

正整数 $N, K$ と 長さ $N$ の非負整数列 $A$ 、 $N$ 頂点 $N$ 辺の単純連結無向グラフが与えられる。頂点には $1,2,\dots,N$ の番号が付けられており、頂点 $i$ には非負整数 $A_i$ が書かれている。

以下の操作を好きな回数行うことができる。

• 辺 と $K \le x \le 2K$ を満たす整数 $x$ を選び、その辺で直接結ばれている $2$ 頂点に書かれた整数をそれぞれ $x$ だけ減らす。

すべての頂点に書かれた整数を $0$ にすることができるか判定し、できるならばそのために必要な操作回数の最小値を求めよ。

制約

• 入力はすべて整数である。
• $3 \le N \le 2 \times 10^5$
• $2 \le K \le 10^9$
• $0 \le A_i \le 10^9$ $(1 \le i \le N)$
• $1 \le u_i,v_i \le N$ $(1 \le i \le N)$
• 与えられるグラフは単純である。
• 与えられるグラフは連結である。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$
$A_1$ $A_2$ $\dots$ $A_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_N$ $v_N$

出力

すべての頂点に書かれた整数を $0$ にするために必要な操作回数の最小値を出力せよ。

不可能な場合は -1 を出力せよ。

サンプル

5 2
2 7 6 3 0
1 2
2 3
3 1
2 4
3 5

3

4 3
3 3 6 6
1 2
2 3
3 4
4 1

2

3 2
10 10 10
1 2
2 3
3 1

6

3 3
6 8 10
1 2
2 3
3 1

-1