题目背景

战争结束了。Doctor Who 终于能休息一会了。他开始整理 TARDIS。

题目描述

Doctor Who 曾有 \(F\) 个敌人，每一个敌人的起源星球都不一样，Doctor Who 曾经打败了他们，并且把他们的照片打印了下来。同时至少有同样数量的相框，被按顺序摆成一行，相框的位置是固定的，供 Doctor Who 放入这些敌人的照片信息。从左到右按 \(1\) 到 \(V\) 顺序编号，\(V\) 是相框的数目。敌人的照片可以移动，并且每张照片用 \(1\) 到 \(F\) 的整数标识。如果\(I<J\)，则照片 \(I\) 必须放在照片 \(J\) 左边的相框中。例如，假设赛博人的标识数为 \(1\)，桑塔人的标识数为 \(2\)，戴立克的标识数为 \(3\)，所有照片在放入相框时必须保持其标识数的顺序，即赛博人必须放在桑塔人左边的相框中，桑塔人必须放在戴立克左边的相框中。如果相框的数目大于照片的数目，则多余的相框必须空，Doctor Who 会甩进他的仓库里。即每个相框只能放一个照片。

每个相框的形状和颜色也不相同（从各个星球买来的），因此，当各个相框中放入不同的照片时，会产生不同的震撼效果，并以震撼值（一个整数）来表示，空置相框的震撼值为 \(0\)。在上面这个例子里，相框与照片的不同搭配所具有的震撼值，可以用如下的表格来表示：

	相框 \(1\)	相框 \(2\)	相框 \(3\)	相框 \(4\)	相框 \(5\)
赛博人	\(7\)	\(23\)	\(-5 \)	\(-24 \)	\(16\)
桑塔人	\(5\)	\(21\)	\(-4\)	\(10\)	\(23 \)
戴立克	\(-21\)	\(5\)	\(-4 \)	\(-20\)	\(20\)

根据表格，赛博人放在相框 \(2\) 中，会显得非常震撼，但若放在相框 \(4\) 中，则显得很辣鸡。

为了取得最佳的震撼效果，必须在保持照片顺序的前提下，使照片的摆放取得最大的震撼值。

格式

输入格式

输入文件的第一行是两个整数 \(F\) 和 \(V\)，分别为照片数和相框数（\(1≤F≤100，F≤V≤100\)）。接下来是矩阵 \(A_{ij}\),它有 \(I\)行，每行 \(J\) 个整数，\(A_{ij}\) 表示照片 \(I\) 摆放在相框 \(J\) 中的震撼值。

输出格式

输出文件的第一行是一个整数，为最大的震撼值；接下来有 \(F\) 行，每行两个数，为那张照片放入那个相框的编号。

样例1

样例输入1

3 5
7 23 -5 -24 16
5 21 -4 10 23
-21 5 -4 -20 20

样例输出1

53