P16530 [THUPC 2026 Final] Block Elimination Game

From the final round of the 2026 Tsinghua University Programming Contest and Collegiate Invitational (THUPC2026). Resources such as the editorial can be found at https://github.com/dapingguo8/THUPC2026-final. > After enjoying the gorgeous illusion photos, everyone was attracted by a nearby block elimination mini-game area. > > On the table, colorful blocks are neatly arranged in piles. As the booth owners, Little T and Little S each provide a magic sieve that can eliminate blocks in batches. The rules are simple: you may use these two sieves repeatedly to eliminate blocks, and the ranking is determined by the total number of blocks remaining on the table.

On the table, there are $n$ piles of blocks arranged neatly. The initial number of blocks in pile $i \ (1 \le i \le n)$ is $a_i$. Little T and Little S provide two magic sieves with mesh sizes $p, q$. They can eliminate blocks in batches by taking the covered piles modulo the corresponding number. When naturally unfolded, each sieve spans exactly $k$ piles in width. They have special elasticity: they can be freely stretched to cover a longer range at both ends, but cannot be compressed inward to cover a shorter range. The sieves are used as follows: - Choose a consecutive block interval $[l, r]$ with length **at least $k$**, and place a sieve over it. - Choose one of the two magic sieves, i.e., choose $m \in \{p, q\}$. - For each pile within $[l, r]$, take its count modulo $m$, i.e., set $a_i \gets a_i \bmod m$. Since you have joined this game, you naturally do not want an average result. To take the top spot on the leaderboard, you want to know: by using the magic sieves any number of times, what is the minimum possible total number of blocks remaining on the table (i.e., $\sum_{i = 1} ^ n a_i$)?

Each test point contains multiple sets of testdata. The first line of the input contains a positive integer $T \ (1 \le T \le 10 ^ 4)$, indicating the number of test cases. For each test case: - The first line contains four positive integers $n, k, p, q \ (1 \le k \le n \le 10 ^ 5, \ 1 \le p < q \le 10 ^ 9)$, representing the number of block piles, the number of piles spanned when a sieve is naturally unfolded, and the mesh sizes of the two magic sieves. - The second line contains $n$ positive integers $a_1, a_2, \dots, a_n \ (1 \le a_i \le 10 ^ 9)$, representing the initial number of blocks in each pile. It is guaranteed that the sum of $n$ over all test cases does not exceed $10 ^ 5$.

For each test case, output one line with a non-negative integer, representing the minimum possible total number of blocks remaining on the table.

For the second test case, one sequence of operations that makes the minimum total number of remaining blocks equal to $11$ is: - Choose interval $[1, 4]$ and use the magic sieve with mesh size $10$, then the remaining block counts become $[1, 1, 9]$. For the third test case, one sequence of operations that makes the minimum total number of remaining blocks equal to $3$ is: - Choose interval $[2, 4]$ and use the magic sieve with mesh size $4$, then the remaining block counts become $[1, 2, 3, 0]$. - Choose interval $[1, 3]$ and use the magic sieve with mesh size $3$, then the remaining block counts become $[1, 2, 0, 0]$. Translated by ChatGPT 5