Description

Given a sequence of positive integers $a_1, \ldots, a_n$ of length $n$ and a positive integer $m$ satisfying $m \geq \max a_i$, you can perform any number of operations (including zero) on the sequence. In each operation, you may select an interval $[l, r]$ and for all $l \leq i \leq r$, set $a_i \gets \left\lfloor \frac{m}{a_i} \right\rfloor$.

Your task is to determine:

1. The maximum possible value of $\sum_{j=1}^n a_j$ achievable through these operations.
2. The minimum number of operations required to achieve this maximum sum.

Input Format

This problem contains multiple test cases.

• The first line contains a positive integer $T$, the number of test cases.
• For each test case:
  • The first line contains two positive integers $n$ and $m$.
  • The second line contains $n$ positive integers $a_1, \ldots, a_n$.

Output Format

For each test case, output two non-negative integers:

1. The maximum possible sum $\sum_{j=1}^n a_j$.
2. The minimum number of operations required to achieve this sum.

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

Hint

Sample Explanation

For the second test case in the sample input, selecting the following 3 intervals achieves the maximum sum of $28$:

1. $[1, 2]$
2. $[2, 5]$
3. $[4, 5]$

It can be proven that this is one of the optimal solutions.

Data Range

This problem uses bundled testing.

• Special Property A: $a_i \leq \sqrt{m}$.
• Special Property B: $a_i$ divides $m$ (i.e., $a_i \mid m$).

For all test cases:

• $1 \leq T \leq 10^5$,
• $1 \leq n \leq 10^5$,
• $1 \leq \sum n \leq 10^6$,
• $1 \leq a_i \leq m \leq 10^{12}$.

Translated by DeepSeek V3.