题目描述

最近 lxhgww 又迷上了投资股票，通过一段时间的观察和学习，他总结出了股票行情的一些规律。

通过一段时间的观察，lxhgww 预测到了未来 $T$ 天内某只股票的走势，第 $i$ 天的股票买入价为每股 $AP_i$，第 $i$ 天的股票卖出价为每股 $BP_i$（数据保证对于每个 $i$，都有 $AP_i \ge BP_i$），但是每天不能无限制地交易，于是股票交易所规定第 $i$ 天的一次买入至多只能购买 $AS_i$ 股，一次卖出至多只能卖出 $BS_i$ 股。

另外，股票交易所还制定了两个规定。

1. 为了避免大家疯狂交易，股票交易所规定在两次交易（某一天的买入或者卖出均算是一次交易）之间，至少要间隔 $W$ 天，也就是说如果在第 $i$ 天发生了交易，那么从第 $i+1$ 天到第 $i+W$ 天，均不能发生交易。
2. 同时，为了避免垄断，股票交易所还规定在任何时间，一个人的手里的股票数不能超过 $MaxP$。

在第 $1$ 天之前，lxhgww 手里有一大笔钱（可以认为钱的数目无限），但是没有任何股票，当然，$T$ 天以后，lxhgww 想要赚到最多的钱，聪明的程序员们，你们能帮助他吗？

输入格式

第 $1$ 行包括 $3$ 个整数，分别是 $T, MaxP, W$。

第 $2 \sim T+1$ 行，第 $i+1$ 行代表第 $i$ 天的股票走势，每行 $4$ 个整数，分别表示 $AP_i, BP_i, AS_i, BS_i$。

输出格式

输出包含一个整数，表示能赚到的做多的钱数。

样例

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

3

样例解释

参数

• $T = 5$ 天
• $MaxP = 2$ 股（最大持股数）
• $W = 0$ 天（交易间隔为 0，即可以连续交易）

每天的数据

天数	买入价(AP)	卖出价(BP)	最多买入(AS)	最多卖出(BS)
1	2	1	1
2
3		2
4		3
5		4

最优策略

1. 第 1 天：买入 1 股，价格 2，花费 2。持股 = 1。
2. 第 2 天：由于 $W=0$，可以交易。但第 2 天价格与第 1 天相同，不操作。
3. 第 3 天：卖出 1 股，价格 2，收入 2。持股 = 0。此时收益为 0（买入花 2，卖出得 2）。
4. 第 3 天：同时可以买入 1 股（因为当天已卖出，但 $W=0$ 允许同一天再买入），价格 3，花费 3。持股 = 1。
5. 第 4 天：卖出 1 股，价格 3，收入 3。持股 = 0。累计收益 = (2-2)+(3-3)=0？等一下，重新计算：
   第 1 天买入花 2，第 3 天卖出得 2，这一步收益 0。
   第 3 天买入花 3，第 4 天卖出得 3，这一步收益 0。
   总收益 0？不对，答案输出 3，说明有更好的策略。

重新寻找最优策略：

1. 第 1 天：不操作。
2. 第 2 天：买入 1 股，价格 2，花费 2。持股 = 1。
3. 第 3 天：卖出 1 股，价格 2，收入 2。收益 0。然后买入 1 股，价格 3，花费 3。持股 = 1。
4. 第 4 天：卖出 1 股，价格 3，收入 3。收益 0。然后买入 1 股，价格 4，花费 4。持股 = 1。
5. 第 5 天：卖出 1 股，价格 5，收入 5。收益 1。
   总收益 = (2-2)+(3-3)+(5-4) = 0+0+1 = 1，仍然不是 3。

再试： 注意 $MaxP=2$，可以持有 2 股。

1. 第 1 天：买入 2 股，价格 2，花费 4。持股 = 2。
2. 第 2 天：不能交易（因为 $W=0$ 允许，但价格不好）。
3. 第 3 天：卖出 2 股，价格 2，收入 4。收益 0。然后买入 1 股，价格 3，花费 3。持股 = 1。
4. 第 4 天：卖出 1 股，价格 3，收入 3。收益 0。然后买入 1 股，价格 4，花费 4。持股 = 1。
5. 第 5 天：卖出 1 股，价格 5，收入 5。收益 1。总收益 1。

检查答案 3 的来源： 实际上最优策略是：

1. 第 1 天：买入 1 股，花费 2。
2. 第 3 天：卖出 1 股，收入 2（收益 0），然后买入 1 股，花费 3。
3. 第 4 天：卖出 1 股，收入 3（收益 0），然后买入 1 股，花费 4。
4. 第 5 天：卖出 1 股，收入 5，收益 1。

还是 1。

可能我理解有误。看样例数据，第 3 天卖出价是 2，买入价是 3，所以同一天卖出再买入会亏损，不应该做。
其实最优是：

1. 第 1 天买入 1 股（2元）。
2. 第 3 天卖出（2元），收益 0。
3. 第 4 天卖出？没有股票了。 等等，也许可以：
4. 第 1 天不买。
5. 第 2 天买入 1 股（2元）。
6. 第 3 天卖出（2元），收益 0。
7. 第 4 天买入？价格 4 元，第 5 天卖出 5 元，收益 1。

还是 1。

但答案是 3，说明我忽略了什么。重新读题：“某一天的买入或者卖出均算是一次交易”，并且两次交易之间至少间隔 $W$ 天。如果 $W=0$，那么同一天可以既买入又卖出吗？题目说“在第 i 天发生了交易，那么从第 i+1 天到第 i+W 天，均不能发生交易”，这意味着第 i 天可以同时进行买入和卖出（都算第 i 天的交易），然后第 i+1 到 i+W 天不能交易。所以同一天买入和卖出是允许的。

那么策略可以是：

1. 第 1 天：买入 2 股（最大持股），花费 4。
2. 第 3 天：卖出 2 股，收入 4，收益 0。同时买入 2 股（价格 3），花费 6。
3. 第 5 天：卖出 2 股，收入 10，收益 4。总收益 4？但持股数限制：第 3 天买入 2 股后持股 2，第 5 天卖出 2 股，收益 = (4-4)+(10-6) = 4。但答案 3，说明不是。

仔细看数据：第 3 天最多买入 1 股（AS=1），所以第 3 天只能买 1 股。
那么：

1. 第 1 天：买入 2 股，花费 4。
2. 第 3 天：卖出 2 股，收入 4，收益 0。买入 1 股，花费 3。
3. 第 5 天：卖出 1 股，收入 5，收益 2。总收益 2。

还是不对。

让我们直接计算样例答案 3 的来源： 一个可能策略：

• 第 1 天：买入 1 股，花费 2。
• 第 2 天：无操作。
• 第 3 天：卖出 1 股，收入 2（收益 0），买入 1 股，花费 3。
• 第 4 天：无操作。
• 第 5 天：卖出 1 股，收入 5，收益 2。 总收益 2。

另一个策略：

• 第 1 天：买入 2 股，花费 4。
• 第 3 天：卖出 1 股，收入 2，买入 1 股，花费 3。持股 = 2。
• 第 4 天：无操作。
• 第 5 天：卖出 2 股，收入 10，收益 = 10-4-3=3。 验证：第 1 天花费 4，第 3 天花费 3，总收入 2+10=12，总花费 7，收益 5？不对。

实际上第 3 天卖出 1 股收入 2，买入 1 股花费 3，净支出 1。总花费 = 4+1=5。第 5 天收入 10，收益 = 10-5=5。但持股数：第 1 天后持股 2，第 3 天后还是持股 2（卖 1 买 1），第 5 天卖 2。收益 5，大于答案 3。

但题目要求最大持股数不超过 2，这里始终不超过 2，应该允许。可能是交易间隔问题：第 3 天进行了卖出和买入两次交易，但 $W=0$ 允许同一天交易，所以可以。那么收益 5 应比答案 3 大，但答案却是 3，说明这个策略不可行？原因可能是：第 3 天卖出和买入算两次交易，但题目说“如果在第 i 天发生了交易，那么从第 i+1 天到第 i+W 天，均不能发生交易”，并没有禁止同一天内的多次交易。所以应该允许。

为什么答案是 3？可能我的计算有误。让我们严格按策略计算现金流： 初始资金无限，记为 0。

1. 第 1 天：买入 2 股，资金 -2*2 = -4。
2. 第 3 天：卖出 1 股，资金 +2；买入 1 股，资金 -3。净资金变化 -1。累计资金 -5。 持股：原 2 股，卖出 1 剩 1，买入 1 变 2 股。
3. 第 5 天：卖出 2 股，资金 +5*2=10。累计资金 5。 最终资金 5，收益 5，但答案 3。

检查题目：卖出价 BP，第 5 天 BP=4，不是 5！我看错了，第 5 天卖出价是 4。表格中第 5 天 AP=5（买入价），BP=4（卖出价）。所以我上面用了错误的卖出价。

更正： 第 5 天卖出价是 4，所以：

• 第 5 天卖出 2 股收入 8。 总资金：-4 -1 +8 = 3。 收益 3，匹配答案。

所以最优策略就是： 第 1 天买入 2 股，第 3 天卖出 1 股并买入 1 股（净持股仍为 2），第 5 天卖出 2 股。

数据范围

• $0 \le W < T \le 2000$
• $1 \le MaxP \le 2000$
• $1 \le BP_i \le AP_i \le 1000$
• $1 \le AS_i \le BS_i \le MaxP$

算法分析

这是一个动态规划问题，涉及状态、交易限制和持股限制。

状态定义

设 $dp[i][j]$ 表示第 $i$ 天结束后，持有 $j$ 股股票的最大现金（利润）。现金越多越好，初始有无限现金，所以初始现金为 0，但买入会减少现金，卖出增加现金。

转移方程

第 $i$ 天可以选择不交易：$dp[i][j] = \max(dp[i][j], dp[i-1][j])$。

如果第 $i$ 天交易（买入或卖出），则上一次交易必须至少在第 $i-W$ 天或之前。设 $pre = \max(0, i-W-1)$，即上次交易可能的最晚天数。

买入

第 $i$ 天买入 $k$ 股（$1 \le k \le AS_i$），买入价为 $AP_i$，买入后持股 $j$，则买入前持股为 $j-k$，现金减少 $k \times AP_i$。 转移：$dp[i][j] = \max(dp[i][j], dp[pre][j-k] - k \times AP_i)$。

卖出

第 $i$ 天卖出 $k$ 股（$1 \le k \le BS_i$），卖出价为 $BP_i$，卖出后持股 $j$，则卖出前持股为 $j+k$，现金增加 $k \times BP_i$。 转移：$dp[i][j] = \max(dp[i][j], dp[pre][j+k] + k \times BP_i)$。

优化

直接转移复杂度为 $O(T \times MaxP \times MaxP)$，太大。

注意到转移是取某个区间内的最大值，可以用单调队列优化。

对于买入： $dp[i][j] = \max_{1 \le k \le AS_i} (dp[pre][j-k] - (j-k) \times AP_i) + j \times AP_i$
设 $f[j] = dp[pre][j] + j \times AP_i$，则 $dp[i][j] = \max_{j-AS_i \le k \le j-1} f[k] - j \times AP_i$。
这是一个滑动窗口最大值问题，可以用单调队列维护 $f[k]$ 递减队列。

对于卖出类似： $dp[i][j] = \max_{1 \le k \le BS_i} (dp[pre][j+k] + (j+k) \times BP_i) - j \times BP_i$
设 $g[j] = dp[pre][j] + j \times BP_i$，则 $dp[i][j] = \max_{j+1 \le k \le j+BS_i} g[k] - j \times BP_i$。

注意：$pre$ 可能是 0，表示之前没有交易。

初始化

$dp[0][0] = 0$，其余为 $-\infty$。

答案

最终答案是 $\max_{0 \le j \le MaxP} dp[T][j]$。

复杂度

优化后复杂度为 $O(T \times MaxP)$，可以通过。