题目描述

给定一个长度为 $n$ 的正整数序列 $a_1, \ldots, a_n$ 以及一个正整数 $m$ 满足 $m \ge \max a_i$。

你可以对序列进行任意次操作（也可以不操作）。每次操作你可以选择一个区间 $[l,r]$，然后对于所有 $l\leq i\leq r$，令 $a_i\gets\bigl\lfloor\frac{m}{a_i}\bigr\rfloor$。

求可以得到的 $\sum_{j=1}^na_j$ 的最大值以及对应的最少操作次数。

输入格式

本题有多组测试数据。

第一行，一个正整数 $T$，表示测试数据组数。对于每组测试数据：

• 第一行，两个正整数 $n,m$。
• 第二行，$n$ 个正整数 $a_1, \ldots, a_n$。

输出格式

对于每组测试数据，一行，两个非负整数，分别表示 $\sum_{j=1}^na_j$ 的最大值以及对应的最少操作次数。

3
2 5
1 2
5 10
1 5 2 4 3
10 10
1 4 2 5 1 6 2 7 1 10

7 1
28 3
80 5

提示

【样例解释】

对于样例的第二组测试数据：选择以下 $3$ 组 $[l,r]$ 即可得到最大值 $28$：

• $[1,2]$；
• $[2,5]$；
• $[4,5]$。

可以证明该方案是最优的之一。

【数据范围】

本题使用捆绑测试。

• 特殊性质 A：$a_i\leq\sqrt m$；
• 特殊性质 B：$a_i\mid m$。

对于所有数据：$1\leq T\leq 10^5$，$1\leq n\leq 10^5$，$1\leq\sum n\leq10^6$，$1\leq a_i\leq m\leq10^{12}$。