20605번 - New Equipments 다국어

Little Q's factory recently purchased $m$ pieces of new equipment, labeled by $1,2,\dots,m$.

There are $n$ workers in the factory, labeled by $1,2,\dots,n$. Each worker can be assigned to no more than one piece of equipment, and no piece of equipment can be assigned to multiple workers. If Little Q assigns the $i$-th worker to the $j$-th piece of equipment, he will need to pay $a_i\times j^2+b_i\times j+c_i$ dollars.

Now please for every $k$ ($1\leq k\leq n$) find $k$ pairs of workers and pieces of equipment, then assign workers to these pieces of equipment, such that the total cost for these $k$ workers is minimized.

The first line contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each test case:

The first line contains two integers $n$ and $m$ ($1 \leq n \leq 50$, $n\leq m\leq 10^8$) denoting the number of workers and the number of pieces of equipment.

Each of the following $n$ lines contains three integers $a_i$, $b_i$, $c_i$ ($1\leq a_i\leq 10$, $-10^8\leq b_i\leq 10^8$, $0\leq c_i\leq 10^{16}$, $b_i^2\leq 4a_ic_i$) describing a worker.

For each test case, output a single line containing $n$ integers, the $k$-th ($1\leq k\leq n$) of which is the minimum possible total cost for $k$ pairs of workers and pieces of equipment.