倒卖配额

残骸堆完了，通风口就在头顶。但最后的关卡不是物理的——是资源的。

"能源配额。"你说，"Zero控制着核心区的能源流通。每天配额价格不同——有时低，有时高。"

"低买高卖？"CC问。

"对。"你说，"我们在废墟里收集了很多配额凭证，现在要在有限天数内倒卖——赚最多。"

"规矩？"

"每天可以买一定量，也可以卖一定量。"你说，"但买之后要隔$W$天才能卖——冷却期。"

"手里最多持多少？"

"有限额。"你说，"最多$MaxP$份。"

"这像赌博。"

"不像。"你说，"价格是已知的——Zero的系统会提前公示。我们是在确定信息下做最优决策。"

"那就是算计。"

"对。"你说，"算计。"

你开始写。$dp[i][j]$为第$i$天持有$j$份配额的最大收益。

"第1天。"你说，"价格5。买10份。$dp[1][10]=-50$。"

"第2天。"你说，"价格3。再买10份。$dp[2][20]=-80$。"

"第$W+2$天。"你说，"价格8。卖10份。$dp[W+2][10]=-80+80=0$。"

"不赚不亏。"

"但如果等到价格10。"你说，"卖20份。$dp[i][0]=-80+200=120$。"

"赚了。"

"对。"

CC把配额凭证摊在金属板上——一张一张，像某种原始的货币。

"我有多少？"她问。

"47张。"你说。

"又是47。"

"对。"你说，"47张配额，47天，47次选择。"

"选对了？"

"我们正在选。"你说，"每一天，每一个买卖决定，都是一次状态转移。"

"转移去哪？"

"去最后。"你说，"去第47天——手里配额清零，收益最大。"

"最大多少？"

"算出来了。"你说，"470。"

"470？"

"对。"你说，"47张配额，每张赚10。"

"够干啥？"

"够买通最后一道门。"你说，"Zero的能源核心——用配额兑换通行权。"

Echo的投影在配额凭证上扫过——像清点，像告别。

"以前Echo-0也倒卖过配额。"她说，"为了买通看守，释放矿工。"

"成功了？"

"释放了三个人。"她说，"然后她被抓了。"

"这次不一样。"你说，"这次我们一起。"

"一起。"

"对。"你说，"sacrifice = 0。"

你按下执行键——最后一行代码运行，屏幕上的数字跳动，最后停在470。

"通了。"你说。

"通了？"CC问。

"通了。"你说，"Zero的门开了。"

Echo的投影开始向门移动——不是飘，是走，一步一步，像某种仪式。

"我进去了。"她说。

"我们——"

"不。"她说，"我自己。"

"Echo——"

"不是消失。"她说，"是融合。等这一切结束……会有人来的。"

她进去了。门在她身后合上。

题目描述

给定未来$T$天的配额价格。每天可以买入或卖出一定量配额，但有交易限额和冷却期$W$。求最大收益。

输入格式

$T,MaxP,W$。然后$T$天的价格$AP_i,BP_i$（买入价和卖出价）和交易限额$AS_i,BS_i$。

输出格式

最大收益。

输入样例

3
1 2 3

输出样例

0

提示

• 单调队列优化DP。
• $dp[i][j]$为第$i$天持有$j$份的最大收益。
• 买：$dp[i][j]=\max(dp[i-W-1][k]-(j-k)\times AP_i)$。
• 卖：$dp[i][j]=\max(dp[i-W-1][k]+(k-j)\times BP_i)$。
• 用单调队列优化$k$的枚举。