C. 双色涂色问题
每个测试的时间限制：2秒
每个测试的内存限制：256 MB

Monocarp 在他的度假小屋安装了一个新的栅栏。栅栏由 $n$ 块相同大小的木板排成一行组成。

Monocarp 决定按照以下规则给栅栏涂色：

1. 每块木板恰好涂成一种颜色；
2. 使用的不同颜色总数恰好为 $2$ 种；
3. 涂成相同颜色的木板必须形成连续的一段，也就是说，对于任意两块涂成相同颜色的木板，它们之间不能有涂成另一种颜色的木板。

Monocarp 有 $m$ 种不同的油漆，第 $i$ 种颜色的油漆最多可以涂 $a_i$ 块木板。Monocarp 不会购买额外的油漆。

你的任务是计算满足 Monocarp 所有要求的涂色方案总数。两种涂色方案被认为是不同的，如果存在至少一块木板在两种方案中颜色不同。

输入格式
第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n, m \le 2 \cdot 10^5$）——木板的数量和 Monocarp 拥有的颜色种类数。

每个测试用例的第二行包含 $m$ 个整数 $a_1, a_2, \dots, a_m$（$1 \le a_i \le n$），其中 $a_i$ 是第 $i$ 种颜色最多能涂的木板数量。

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

输出格式
对于每个测试用例，输出满足所有要求的涂色方案总数。

输入输出样例

输入：

3
5 2
2 4
5 2
3 4
12 3
5 9 8

输出：

4
6
22

样例解释

在第一个测试用例中，共有 $4$ 种不同的涂色方案（从左到右木板颜色编号的序列如下）：

• $[1,2,2,2,2]$
• $[1,1,2,2,2]$
• $[2,2,2,1,1]$
• $[2,2,2,2,1]$

在第二个测试用例中，共有 $6$ 种不同的涂色方案：

• $[1,2,2,2,2]$
• $[1,1,2,2,2]$
• $[1,1,1,2,2]$
• $[2,2,1,1,1]$
• $[2,2,2,1,1]$
• $[2,2,2,2,1]$