背景

尛焱轟有很多妹子。。。

描述

尛焱轟有n个妹子,他想和这些妹子做m件事情,所以他要把这些妹子分成m组(可以有空组),第j组的妹子要和尛焱轟做第j个事情。然而,第i个妹子对第j个事情的讨厌程度是a[i][j],分好组后,第j组的所有妹子对第j个事情的讨厌程度的最大值称为第j组的不愉悦度(如果第j组没有人则不愉悦度为0)。总的不愉悦度就是m个组的不愉悦度的总和。如何分组能让这个总和最小呢?

输入格式

第一行两个用空格隔开的整数n和m。接下来n行每行m个整数表示每个a[i][j]。

输出格式

一个整数,表示最小不愉悦度总和的值。

样例输入

3 3
1 2 100
100 4 5
1 100 3

样例输出

5

数据范围与约定

本题共10个数据,除样例外,n×m=362880,所有的a[i][j]是在[1,1000000000]范围等概率随机生成的,m=1,2,3,4,5,6,7,8,9各占用一组数据。

样例解释

第1组:妹子1和妹子3,最大的讨厌程度是1。

第2组:妹子2,最大的讨厌程度是4。

第3组:没有人。

总的不愉悦度是5。

来源

经典题目