Allocating Machines to Companies

Background

Special for beginners, ^_^

Problem Description

The head office owns $M$ highly efficient machines and plans to distribute them among its $N$ branch companies. If a branch company receives these machines, it can generate a certain profit for the country. Question: how to allocate the $M$ machines so that the profit for the country is maximized? Find the maximum profit value. Here $M \le 15$, $N \le 10$. Allocation rule: each company may receive any number of machines, but the total number allocated cannot exceed $M$. If there are multiple optimal solutions, the earlier companies should receive as few machines as possible.

Input Format

The first line contains two numbers: the first is the number of branch companies $N$, and the second is the number of machines $M$.

This is followed by an $N \times M$ matrix; the value at position $(i,j)$ is the profit obtained when the $i$-th company is allocated $j$ machines.

Output Format

The first line is an integer: the maximum profit.

This is followed by $N$ lines, each with two integers $a$ and $b$, meaning that company $a$ is allocated $b$ machines.

Sample Input 1

2 15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 2

Sample Output 1

2
1 0
2 15

Constraints

1s, 1024KiB for each test case.