P2066 Machine Allocation

The head office has $M$ high-efficiency machines to distribute to $N$ subsidiary companies. If a company receives a certain number of machines, it can generate a corresponding profit for the country. How should these $M$ machines be allocated to maximize the total profit? Find the maximum profit. Constraints: $M \le 15$, $N \le 10$. Allocation rule: each company may receive any number of machines, but the total number cannot exceed $M$. If multiple allocations yield the same maximum profit, break ties by making earlier-indexed companies receive as few machines as possible, that is, minimize $x_1$; if still tied, minimize $x_2$; and so on.

The first line contains two numbers: the number of companies $N$ and the number of machines $M$. Then follows an $N \times M$ matrix. The entry at row $i$ and column $j$ gives the profit when company $i$ is assigned $j$ machines.

The first line contains the maximum profit. Then output $N$ lines. In the $i$-th line, output the number $x$ of machines assigned to company $i$.

Translated by ChatGPT 5