题目描述

总公司有M台设备，准备分给N个分公司。已知第i个分公司获得j台设备时的盈利；没有获得设备时盈利为0。

每个分公司可以获得任意非负整数台设备，分配总数不能超过M，可以有剩余设备。请最大化总盈利，并输出一种分配方案。

输入格式

第一行两个整数N、M。接下来N行，每行M个非负整数，第i行第j个数表示第i个公司获得j台设备的盈利。

输出格式

第一行输出最大总盈利。接下来N行，第i行输出公司编号i和该公司分得的设备数。

本题使用特殊评测，有多种最优方案时输出任意一种。

样例

3 3
30 40 50
20 30 50
20 25 30

70
1 1
2 1
3 1

数据范围

1≤N≤10，1≤M≤15；每个盈利值在0至10000之间。