P17297 [ICPC 2026 Xi'an I] Qenerals

Yuki is playing a game called Qenerals. At time $t = 0$, Yuki has $x = 0$ soldiers and occupies $y = 1$ fortress. There are $n$ unoccupied fortresses on the map, where the $i$-th fortress has a parameter $a_i$. The game lasts for $m$ seconds. For each positive integer $i$ such that $1 \le i \le m$: - At the beginning of the $i$-th second, each fortress occupied by Yuki produces $1$ soldier, i.e., $x \leftarrow x + y$. - At the end of the $i$-th second, Yuki can perform any number of operations (including zero). In each operation, Yuki chooses an unoccupied fortress $j$ such that $a_j \le x$, consumes $a_j$ soldiers, and occupies fortress $j$, i.e., $x \leftarrow x - a_j$ and $y \leftarrow y + 1$. You need to help Yuki determine the maximum number of soldiers she can have after the game ends.

This problem contains multiple test cases. The first line contains a positive integer $t$ $(1 \le t \le 10^5)$, representing the number of test cases. For each test case: - The first line contains two positive integers $n, m$ $(1 \le n \le 5\cdot10^5,\ 1 \le m \le 10^{9})$. - The second line contains $n$ positive integers $a_1, \dots, a_n$ $(1 \le a_i \le 10^9)$. It is guaranteed that the sum of $n$ over all test cases does not exceed $5\cdot10^5$.

For each test case, output a single line containing an integer representing the maximum number of soldiers Yuki can have after the game ends.

For the first test case: - At the beginning of the $1$-st second, the number of fortresses occupied by Yuki is $y = 1$, so the number of soldiers $x$ increases from $0$ to $1$. - At the end of the $1$-st second, Yuki can choose to occupy the $2$-nd fortress, so $y$ increases from $1$ to $2$, and $x$ decreases from $1$ to $0$. - At the beginning of the $2$-nd second, $y = 2$, so $x$ increases from $0$ to $2$. - At the end of the $2$-nd second, Yuki can choose not to perform any operations. - At the beginning of the $3$-rd second, $y = 2$, so $x$ increases from $2$ to $4$. - At the end of the $3$-rd second, Yuki can choose not to perform any operations. - After the game ends, the number of soldiers $x$ is $4$. It can be proven that $4$ is the maximum number of soldiers Yuki can have. For the second test case: - Yuki can occupy the $1$-st, $2$-nd, and $3$-rd fortresses at the end of the $1$-st, $2$-nd, and $3$-rd seconds respectively, allowing her to have $13$ soldiers after the game ends. For the third test case: - Yuki can occupy the $1$-st fortress at the end of the $1$-st second, and the $2$-nd and $3$-rd fortresses at the end of the $2$-nd second, allowing her to have $12$ soldiers after the game ends.