题目描述

给定一个 n*m 的矩阵,矩阵中每一个格子都有一个正权值 Ai现在你可以选出一些格子出来,而且要满足每一行每一列都至多选一个格子。定义一个方案 S 的权值为:

$$\frac{\sum_{u\in S}A_u}{\mid S\mid +1}$$

请求出权值最大的方案的权值并以最简分式的形式输出。特别地,如果结果是整数,则输出形如 x/1 分式。

输入格式

输入第一行两个正整数 n,m。

接下来 n 行,每行 m 个正整数,描述这个矩阵。

输出格式

一个最简分数,表示权值最大的方案的权值。

样例输入

2 2

1 9

9 10

样例输出

6/1

数据范围及约定

测试点 n,m Ai 特殊性质
1 <= 2 <= 109
2 <= 4 <= 109
3 <= 8 <= 109
4 <= 16 <= 16
5 <= 32 <= 32 所有Ai都相等
6 <= 32 <= 32
7,8,9,10 <= 64 <= 109