B20 实践-2 吃饺子

题目描述

佩奇一家人到爷爷家过年， 爷爷煮了很多饺子， 并把饺子摆成了一个 $n$ 行 $m$ 列的矩阵， 每个饺子 都有一个值表示它的大小。爷爷告诉佩奇， 他每列只能挑一个饺子吃。佩奇想吃到总休积最大的饺子，也就是说挑出来的饺子的大小之和最大， 他应该怎么挑饺子呢？

输入格式

第一行两个整数 $n,m$；

接下来 $n$ 行每行 $m$ 个数 $val_{i,j}$ ，表示第 $i$ 行第 $j$ 列饺子的大小。

输出格式

输出一个整数，表示最大的和。

样例输入

3 4
1 2 4 3
3 2 4 1
4 1 3 2

样例输出

13

数据范围

对于 $100\%$ 的数据： $1\le N,M,val_{i,j}\le 1000$ 。