問題文

$N$ 個の足場がある. これらはそれぞれ足場 $1$, 足場 $2$, $\cdots$, 足場 $N$ の順に名付けられている. 足場 $i~(1 \leq i \leq N)$ の高さは $H_i$ である.

また, $M$ 個の階段があり, $j~(1 \leq j \leq M)$ 番目の階段は足場 $X_j$ と足場 $Y_j$ を $\left|H_{X_j}-H_{Y_j} \right|$ 段の階段で双方向に繋いでいる. なお, 階段で繋いでいる $2$ つの足場の高さが等しいことはない.

これらの階段を用いてある足場から別の足場へ移動することができる. 厳密には, 階段を用いて足場 $a$ から足場 $b$ へ移動するような移動について,

• $H_a < H_b$ ならば, $(H_b-H_a)$ 段の階段を上って足場 $a$ から足場 $b$ へ移動する.
• $H_a > H_b$ ならば, $(H_a-H_b)$ 段の階段を下って足場 $a$ から足場 $b$ へ移動する.

今, チェリーちゃんとゼルコバ君がいる. この2人の状況と達成したい目標, 条件は以下の通りである.

• チェリーちゃん: 最初, 足場 $1$ にいる. $0$ 個以上の階段を用いて移動することによって, 足場 $N$ へ移動したい. ただし, 階段を用いて足場 $a$ から足場 $b$ へ移動する場合, $a \lt b$ を満たしていなければならない. つまり, 足場の番号が増加するような移動でなければならない.
• ゼルコバ君: 最初, 足場 $N$ にいる. $0$ 個以上の階段を用いて移動することによって, 足場 $1$ へ移動したい. ただし, 階段を用いて足場 $a$ から足場 $b$ へ移動する場合, $a \gt b$ を満たしていなければならない. つまり, 足場の番号が減少するような移動でなければならない.
• 2人共通: 階段を用いた足場の移動において, 2回連続で階段を上るような移動はできない.

チェリーちゃんとゼルコバ君それぞれについて以下の問に答えよ.

• 条件を満たしながら足場を移動して目標を達成できるか? また, $2$ 人とも階段を上ることが大好きなため, 目標を達成できるならば移動における上る段数 (下る段数についてはカウントしない) の総和の 最大値 を求めよ.

制約

• $2 \leq N \leq 10^5$
• $1 \leq M \leq 1.5 \times 10^5$
• $0 \leq H_i \leq 10^9 \quad (1 \leq i \leq N)$
• $1 \leq X_j \lt Y_j \leq N \quad (1 \leq j \leq M)$
• $H_{X_j} \neq H_{Y_j} \quad (1 \leq j \leq M)$
• $j \neq k \Rightarrow (X_j, Y_j) \neq (X_k, Y_k) \quad (1 \leq j \leq M, 1 \leq k \leq M)$
• 入力は全て整数である.

入力

$N$ $M$
$H_1$ $\cdots$ $H_N$
$X_1$ $Y_1$
$\vdots$
$X_M$ $Y_M$

出力

出力は $2$ 行からなる.

• $1$ 行目にはチェリーちゃんについて, 条件を満たしながら足場を移動することが不可能な場合, -1 と出力し, 可能な場合, 上る段数の総和の最大値を出力せよ.
• $2$ 行目にはゼルコバ君について, 条件を満たしながら足場を移動することが不可能な場合, -1 と出力し, 可能な場合, 上る段数の総和の最大値を出力せよ.

最後に改行を忘れないこと.

サンプル

5 5
0 10 15 5 20
1 5
1 2
2 3
3 4
4 5

20
10

3 2
4 6 46
1 2
2 3

-1
0

8 10
31 41 59 26 53 58 97 93
1 8
2 7
3 5
1 4
5 8
4 5
2 5
6 7
4 7
3 7

62
5

4 1
1 2 3 4
2 3

-1
-1