该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在连续出题的几天里，出题人没活了，只能咬打火机了。

但很不幸的是，打火机炸缸了，出题人被炸出了走马灯。

他想起了两年前刚入社的那段时光，自己什么都不会，是个写 $\texttt{Dijkstra}$ 会忘了改小根堆、写二分一直 $\texttt{TLE}$、不会算值域一直 $\texttt{\#define int long long}$、线段树经常写 $\texttt{RE}$、…………、码风极其丑陋的神人。

同时他想起了那时不会做的一个题，他发现这题非常适合出，于是放了进来。

题目描述

给定 $n$ 个整数序列，每个序列的长度均为 $m$。你可以将这 $n$ 个序列作为一个个整体，按照任意的顺序进行全排列。

排列完成后，将它们按顺序首尾相接，拼成一个长度为 $n \times m$ 的长序列，记为 $a$（序列下标从 $1$ 开始，即 $a_1, a_2, \dots, a_{n \times m}$）。

你的任务是寻找一种最优的排列顺序，使得拼接后的长序列 $a$ 的加权和最大。长序列加权和的计算公式为：

输入格式

第一行包含两个整数 $n$ 和 $m$（$1\le n, m\le 10^5$，$1\le n \times m \le 10^5$），分别表示序列的数量和每个序列的长度。

接下来 $n$ 行，每行包含 $m$ 个整数。其中第 $i$ 行的第 $j$ 个整数表示第 $i$ 个序列的第 $j$ 个元素的值 $a_{i, j}$（$1\le a_{i,j} \le 10^8$）。

输出格式

输出一个整数，表示在所有可能的拼接顺序中，能够获得的最大加权和。

样例

2 3
3 1 2
1 1 1

35

数据范围

共有 $25$ 组测试点。

对于前 $5$ 组测试点，$1\le n\times m\le 20$。

对于后 $20$ 组测试点，$1\le n\times m\le 10^5$。