‹ 上一题 下一题 ›

s09244. 双档换购 未做

1000 ms 256 MB 测试点 10 S-06·贪心进阶与反悔贪心反悔堆

题目描述

市场上流通一种通用份额,连续 天开市。第 天给出两个档位的报价:普惠档买入价 与精选档卖出价 ,保证 。份额不分档:任意一天买入的份额,之后任意一天都可以卖出,卖出收款按当日精选档价结算。

每天你至多买入一份(按当日 付款),至多卖出一份(按当日 收款,卖出前必须持有);同一天可以先买后卖。持有数量没有上限,卖出时退掉手中的哪一份由你决定。

求 天结束后能取得的最大总收益。

输入格式

第一行一个整数 。

接下来 行,第 行两个整数 。

输出格式

一行一个整数,表示最大总收益。

样例 1

样例

输入
4
1 3
2 10
8 9
1 12
输出
27

一种最优方案:第 天买 份并在第 天以 卖出,得 ;第 天买 份当天以 卖出,得 ;第 天再买 份(价 );第 天买 份(价 )当天以 卖出,得 。合计 。

样例 2

每天先以 买入一份、再以 卖出,每天得 ,三天合计 。

数据范围

;。

总收益可能超过 位整数范围。

输入
输出

            
答案