Calc CH Round #64 - MFOI杯水题欢乐赛 day1

题目描述

给定一个 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 无