题目描述

总公司拥有 $m$ 台高效设备，准备分给下属的 $n$ 个分公司。每个分公司获得不同数量的设备时，可以产生不同的盈利。

每个公司可以获得任意数量的设备，但所有公司获得的设备总数不能超过 $m$。请计算如何分配设备，才能使总盈利最大。

若有多种最优方案，输出字典序最小的方案。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示分公司数量和设备数量。

接下来 $n$ 行，每行包含 $m$ 个整数。第 $i$ 行第 $j$ 个整数表示第 $i$ 个分公司分配 $j$ 台设备时的盈利。

输出格式

第一行输出一个整数，表示最大盈利值。

接下来 $n$ 行，每行输出两个整数 $i$ 和 $x$，表示第 $i$ 个分公司分配 $x$ 台设备。

3 3
30 40 50
20 30 50
20 25 30

70
1 1
2 1
3 1

数据范围与提示

• $1 \le n \le 100$
• $1 \le m \le 100$