問題文

正整数 $n, m$ と長さ $n$ の非負整数列 $L = (L _ 1, L _ 2, \ldots, L _ n),\ R = (R _ 1, R _ 2, \ldots, R _ n)$ が与えられます。

長さ $m$ の数列 $A = (A _ 1, A _ 2, \ldots, A _ m)$ が よい列 であるとは、次の $2$ つの条件を全て満たすことを言います。

• 全ての $i \in\lbrace 1, 2, \ldots, m\rbrace$ に対して、$A _ i$ は $1$ 以上 $n$ 以下の整数である。
• 全ての $x\in\lbrace 1, 2, \ldots, n\rbrace$ に対して、$A _ i = x$ を満たす $i \in\lbrace 1, 2, \ldots, m\rbrace$ の個数は $L _ x$ 以上 $R _ x$ 以下である。

よい列 が存在するかを判定し、存在する場合は よい列 の転倒数としてあり得る最大値を求めてください。

ここで、長さ $k$ の数列 $A = (A _ 1, A _ 2, \ldots, A _ k)$ の転倒数は、$1\leq i \lt j \leq k$ かつ $A _ i \gt A _ j$ を満たす整数組 $(i, j)$ の個数と定義されます。

$T$ 個のテストケースが与えられるので、その全てについて上記の問題を解いてください。

入力

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

まず、$1$ 行目にテストケースの個数 $T$ が以下の形式で与えられる。

$T$

$i\ (1\leq i\leq T)$ 個目のテストケースは $3i - 1, 3i, 3i + 1$ 行目に以下の形式で与えられる。

$n\ m$
$\begin{matrix}
L _ 1 \ L _ 2 \ \cdots\ L _ n \newline
R _ 1 \ R _ 2 \ \cdots\ R _ n
\end{matrix}$

• 入力は全て整数で与えられる。
• $1\leq T \leq 2\times 10 ^ 5$
• $1\leq n \leq 2\times 10 ^ 5$
• $1\leq m \leq 10 ^ 9$
• $0\leq L _ i \leq R _ i \leq 10 ^ 9$
• $T$ 個のテストケースにわたる $n$ の総和は $2\times 10 ^ 5$ 以下である。

出力

$T$ 行出力してください。$i\ (1\leq i\leq T)$ 行目には 、$i$ 個目のテストケースについて、よい列 が存在しない場合は -1 を、存在する場合は よい列 の転倒数としてあり得る最大値を出力してください。

$T$ 行目の出力のあとも改行してください。

サンプル

3
3 3
0 0 2
0 2 3
3 4
1 2 3
4 5 6
2 1000000000
0 0
1000000000 1000000000

2
-1
250000000000000000