题目描述

小球有从 $1$ 到 $m$ 共 $m$ 种不同的颜色，Alice 有 $a_i$ 个第 $i$ 种颜色的小球和 $n$ 个空盒子。

如果每个球都放进了一个盒子，并且每个盒子内所有球都不同色，那么这个放置小球的方案是有效的。

在所有有效的放置方案中，装有 $m$ 个小球的盒子数量越少越好，Alice 希望你求出这个最小值。

保证至少有一个有效的放置方案（$a_i\leq n$）。

输入格式

第一行一个整数 $T$ 代表数据组数，对于每组数据：

第一行两个整数 $n,m$ 表示空盒子数和颜色数。

第二行 $m$ 个整数 $a_1,a_2,\cdots,a_m$ 表示每种颜色的球数。

输出格式

对于每组数据，一行一个整数表示答案。

1
5 3
5 4 4

3

样例解释 1

用 3 个盒子装三个颜色的球各一个 第 4 个盒子装颜色为 1,2 的球各一个 第 5 个盒子装颜色为 1,3 的球各一个。

数据范围

对于 $30\%$ 的数据，$T=1$，$n\leq 5$，$m\leq 5$。

对于 $60\%$ 的数据，$T=1$，$n,m\leq 1000$。

对于 $100\%$ 的数据，$1\leq T\leq 10$，$1\leq n,m\leq 10^5$，$1\leq a_i\leq n$。