Description

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.

Input Format

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.

Output Format

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$.

3 3
30 40 50
20 30 50
20 25 30

70
1 1
2 1
3 1

Hint

Translated by ChatGPT 5