2002: 这次不是X额宝

内存限制:256 MB 时间限制:1 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:128 通过:37

题目描述

【理财有风险,投资需谨慎】
Alice这次决定去股市里当一波韭菜。
她希望你设计一个算法,在满足以下3个约束条件下,计算出最大利润。
1、  你可以多次买卖一支股票,但是对于每支股票,你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
2、  因为周转资金需要时间,Alice在买入股票前(第一次除外)需要等一天的时间。即在卖出当天的后天才能进行下一次买入。
3、  为了方便计算,你不用考虑持股数、Alice是否买得起等问题。每次买卖获得的利润就是卖出价减去买入价。

输入格式

第一行股票样个数N(1<=N<=100),天数M(1<=M<=100)。
接下来N行每行包含M个整数,分别表示这只股票第i天的股价(1<=Pi<=10000)。

输出格式

输出一个数字,表示Alice的最大盈利。

输入样例 复制

2 5
1 2 3 0 2
0 0 5 4 3

输出样例 复制

8

数据范围与提示

对于第一支股票会做两次买卖:
        第一天买入,第二天卖出,盈利1元。
        第四天买入(第三天筹集资金不能买入),第五天卖出,盈利2元。
对于第二支股票:
        第一天或者第二天买入,第三天之后卖出,盈利5元。
一共盈利8元。