馕

题号：NC53273
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
Special Judge, 64bit IO Format: %lld

题目描述

题目译自 JOISC 2019 Day1 T3「ナン / Naan」

JOI咖喱店以提供很长（？）的馕而闻名。它提供的馕有L种口味，编号从1到L。「JOI特色馕」是店内最受欢迎的一道菜。馕的总长度为L厘米。我们定义「点X」为馕上距离馕左端X厘米处的点。对于 $1 \le j \le L$ ，点j-1和点j间的一段馕是第j种口味的。
有N个人来到了JOI咖喱店，他们每个人的偏好都不同，具体的说，第i个人每吃一厘米的风味j的馕，就会获得 $V_{i,j}$ 的快乐度。
他们只买了一个JOI特色馕，他们将用下面的方式分享馕：

选择N-1个分数 $X_1, \ldots ,X_{N-1}$ ，满足 $0\lt X_1\lt X_2\lt \ldots \lt X_{N-1}\lt L$ 。
选择N的一个排列 $P_1, \ldots P_N$ 。
对于每一个 $k(1 \le k \le N-1)$ ，在点 $X_k$ 的位置切一刀，然后馕将被切成N个部分。
第 $k(1 \le k \le N)$ 个部分的左端点为 $X_{k-1}$ ，右端点为 $X_{k}$ ，这里我们认为 $X_0=0,X_N=L$ 。
第 $P_i$ 个人将吃掉第i个部分。

现在他们想公平的分配馕，他们认为一种分配方法是公平的，当且仅当每个人获得的快乐度都不小于他们独吞整个馕所获得的快乐度的 $\frac{1}{N}$ 。

现在给你N个人的信息，你需要判断是否存在一种公平的分配方式，如果存在，输出一组分配方案。

输入描述:

从标准输入中读取数据。
第一行两个整数N,L。
接下来N行，每行L个整数，第i行第j个数为。

输出描述:

输出数据到标准输出中。
如果无解，输出一行-1；
如果有解，首先输出N-1行，第i行两个整数，要求是一对满足的整数对。
接下来一行N个整数，第i个数表示。
你的输出需要满足：
。
。
是一个1,...,N的排列。第i个人获得的总快乐度不小于。
不必互质。
可以证明，如果输入数据有解，那么一定存在一组满足上述条件的解。

示例1

输入

复制

2 5
2 7 1 8 2
3 1 4 1 5

输出

复制

14 5
2 1

说明

在这组样例中，第一个人如果吃掉整个馕，会得到2+7+1+8+2=20的快乐度，第二个人如果吃掉整个馕，会获得3+1+4+1+5=14的快乐度。因此，如果第一个人获得不小于的快乐度，且第二个人获得不小于的快乐度，就是一组合法的解。
如果在点的位置切一刀，第一个人会获得的快乐度，第二个人会获得的快乐度。因此这是一组合法的解。

示例2

输入

复制

输出

复制

1 7
2 7
3 7
4 7
5 7
6 7
3 1 4 2 7 6 5

说明

在这组样例中，馕只有一种风味。只要把馕七等分，就是合法的方案，与无关。

示例3

输入

复制

输出

复制

说明

注意不必互质。

备注:

对于所有输入数据，有。

Checker by @EntropyIncreaser
CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/3032