Maximum Coin Collection

Cpg is touring a dream city that features n money trees. Each day, every tree drops a different number of coins. However, since Cpg can only stay in the city for k days, he can only cut down one tree per day and claim all the coins that fall from that tree on that day. Note that once a tree is cut, it cannot be used on any subsequent day.

You are given an integer n (the number of trees) and an integer k (the number of days). Then follow n lines, each containing k integers. The j-th integer on the i-th line, denoted by \(a_{i,j}\), represents the number of coins that will drop from the i-th tree on day \(j\).

Your task is to determine the maximum number of coins Cpg can collect over the k days. Formally, you need to select exactly k distinct trees and assign each one a unique day \(j\) (with \(1 \le j \le k\)), so as to maximize the total coins collected, i.e.,

[ \text{maximize} \quad \sum_{j=1}^{k} a_{p_j,j}, ]

where \(p_j\) is the index of the tree cut on day \(j\), and all \(p_j\) are distinct.

Note: If \(n > k\), you will select only k trees. You may assume that the input values are such that an optimal strategy always exists.

inputFormat

The first line contains two integers n and k separated by a space.

Then follow n lines, each containing k integers. The j-th integer of the i-th line represents \(a_{i,j}\), the coins collected if the i-th tree is cut on day \(j\).

outputFormat

Output a single integer, which is the maximum number of coins Cpg can collect.

sample

3 2
1 2
3 4
5 1

9