题目描述
市场上流通一种通用份额,连续 天开市。第 天给出两个档位的报价:普惠档买入价 与精选档卖出价 ,保证 。份额不分档:任意一天买入的份额,之后任意一天都可以卖出,卖出收款按当日精选档价结算。
每天你至多买入一份(按当日 付款),至多卖出一份(按当日 收款,卖出前必须持有);同一天可以先买后卖。持有数量没有上限,卖出时退掉手中的哪一份由你决定。
求 天结束后能取得的最大总收益。
输入格式
第一行一个整数 。
接下来 行,第 行两个整数 。
输出格式
一行一个整数,表示最大总收益。
样例 1
样例
输入
4 1 3 2 10 8 9 1 12
输出
27
一种最优方案:第 天买 份并在第 天以 卖出,得 ;第 天买 份当天以 卖出,得 ;第 天再买 份(价 );第 天买 份(价 )当天以 卖出,得 。合计 。
样例 2
输入
3 5 6 5 6 5 6
输出
3
每天先以 买入一份、再以 卖出,每天得 ,三天合计 。
数据范围
;。
总收益可能超过 位整数范围。