P16228 [Lanqiao Cup 2026 NOI Qualifier A] Read Commands

You are managing an old linear mechanical hard drive, which is divided into $N$ consecutive sectors (numbered from $1$ to $N$). Because of a special allocation rule of the file system, the amount of data stored in sector $i$ is $C \times i$ bytes (where $C$ is a constant representing the system cluster size). For example, when $C = 2$, the data sizes in sectors $1$ to $4$ are $2, 4, 6, 8$ bytes. Now you need to read exactly $W$ bytes of data from this hard drive for recovery. To minimize head-seeking cost, you are only allowed to send “read commands” to the drive. Each command can specify a continuous sector interval $[l, r]$ and read all data in that interval. Find the minimum number of read commands needed to read exactly $W$ bytes. Note: each sector can be read at most once. If it is impossible to make the total exactly $W$ bytes, output $-1$.

The first line contains an integer $T$, representing the number of test cases. The next $T$ lines each contain three integers $N, C, W$, separated by spaces.

For each test case, output one integer per line, representing the minimum number of read commands. If it is impossible, output $-1$.

### Constraints and Notes For $30\%$ of the test cases, $1 \le N \le 1000$, and $T = 2$. For all test cases, $1 \le N \le 10^5$, $2 \le T \le 10$, $1 \le C \le 100$, $0 \le W \le 10^9$. Translated by ChatGPT 5