1044.花瓶插花

Time Limit: 1000 MS    Memory Limit: 32768 KB
Total Submission(s): 658    Accepted Submission(s): 167

Description

有m朵花和n个花瓶,要把这些花全部插入某些花瓶中,花瓶和花都是有序的,花在花瓶中的先后顺序必须与给定顺序相同,每朵花插入每个花瓶能得到的美观程度都不一定相同,选择一些和花瓶,求插花能得到的最大美观程度。

Input

第一行是两个整数m, n(1 <= m <= n <= 1000),表示花的数量和花瓶的数量。之后m行,每行n个正整数(<= 100),这m行中第i行的第j个数字表示第i朵花插入第j个花瓶的美观程度。

Output

一个整数,最大的总美观程度。

Sample Input

3 5
5 9 3 2 4
1 3 2 9 5
4 2 1 3 5

Sample Output

23

Source

Unknown