E2. 乌龟与逆序对（困难版）
每测试点时间限制：$2$ 秒
内存限制：$512$ 兆字节

这是本题的困难版本。两个版本的区别在于对 $m$ 的约束以及简单版本中对每个 $i$ 从 $1$ 到 $m-1$ 有 $r_i < l_{i+1}$。只有同时解决了两个版本，你才能进行 Hack。

乌龟给了你 $m$ 个区间 $[l_1, r_1], [l_2, r_2], \dots, [l_m, r_m]$。
他认为一个排列 $p$ 是有趣的，当且仅当：
对于每个区间 $i$ 存在一个整数 $k_i$（满足 $l_i \le k_i < r_i$），并且令

$$a_i = \max_{j = l_i}^{k_i} p_j, \quad b_i = \min_{j = k_i+1}^{r_i} p_j $$

对于每个 $i = 1, 2, \dots, m$，下面的条件成立：

$$\max_{i=1}^m a_i \;<\; \min_{i=1}^m b_i$$

乌龟希望你在所有长度为 $n$ 的有趣排列中，计算逆序对的最大个数，如果不存在有趣的排列，则输出 $-1$。

逆序对的定义：在排列 $p$ 中，一对 $(i, j)$（$1 \le i < j \le n$）满足 $p_i > p_j$ 称为一个逆序对。

---

输入格式
每个测试点包含多个测试用例。第一行包含整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。
每个测试用例的第一行包含两个整数 $n, m$（$2 \le n \le 5 \cdot 10^3$，$0 \le m \le 5 \cdot 10^3$），分别表示排列长度和区间个数。
接下来 $m$ 行，第 $i$ 行包含两个整数 $l_i, r_i$（$1 \le l_i < r_i \le n$），表示第 $i$ 个区间。注意可能存在相同的区间（即可能存在两个不同的下标 $i, j$ 使得 $l_i = l_j$ 且 $r_i = r_j$）。

所有测试用例的 $n$ 之和不超过 $5 \cdot 10^3$，$m$ 之和也不超过 $5 \cdot 10^3$。

---

输出格式
对于每个测试用例，如果没有有趣的排列，输出一行一个整数 $-1$。
否则输出一行一个整数，表示最大的逆序对数。

---

样例输入

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

样例输出

1
0
8
18
-1
-1
15
15

---

样例解释
第三个测试用例中，逆序对数最大的有趣排列是 $[5,2,4,3,1]$。

第四个测试用例中，逆序对数最大的有趣排列是 $[4,3,8,7,6,2,1,5]$。此时我们可以取 $[k_1, k_2, k_3] = [2,2,7]$。

第五个和第六个测试用例中，可以证明不存在有趣的排列。

第七个测试用例中，逆序对数最大的有趣排列是 $[4,7,6,3,2,1,5]$。此时我们可以取 $[k_1, k_2, k_3, k_4] = [1,6,1,6]$。

第八个测试用例中，逆序对数最大的有趣排列是 $[4,7,3,6,2,5,1]$。