P13009 【MX-X13-T4】"KDOI-12" Competitiveness is Human Nature, Utility is Society's Nature

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.

**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$.

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.

### **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.** | Subtask | Points | $n \leq$ | $\sum n \leq$ | Special Properties | |:--:|:--:|:--:|:--:|:--:| | $1$ | $9$ | $4$ | $400$ | None | | $2$ | $27$ | $10^3$ | $10^4$ | None | | $3$ | $11$ | $10^5$ | $10^6$ | A | | $4$ | $16$ | $10^5$ | $10^6$ | B | | $5$ | $37$ | $10^5$ | $10^6$ | None | - **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.*