Description

The headquarters has M units of high-efficiency equipment, which are to be distributed among its N subsidiaries.
Each subsidiary can generate a certain profit for the country if it receives these devices.
Question: How should these M units of equipment be allocated to maximize the country's profit? Determine the maximum profit value.
Constraints: M ≤ 100, N ≤ 100.
Allocation principle: Each company may receive any number of devices, but the total number must not exceed M.

Input Format

The first line contains two numbers: the first is the number of subsidiaries N, and the second is the number of equipment units M.
The following is an N*M matrix indicating the profit generated when the I-th company is allocated J units of equipment.

Output Format

The first line outputs the maximum profit value.
The next N lines each contain two numbers: the subsidiary number and the number of equipment units allocated to it.

3 3           //3个分公司分3台机器
30 40 50
20 30 50
20 25 30

70                                         //最大盈利值为70
1 1                                        //第一分公司分1台
2 1                                        //第二分公司分1台
3 1                                        //第三分公司分1台