股票交易

题目描述

Y 同学最近迷上了股票投资。通过长时间的观察和学习，他掌握了某只股票在未来 $T$ 天内的行情规律。

已知第 $i$ 天（$1 \le i \le T$）的股票交易信息如下：

• 买入价：每股 $AP_i$ 元。
• 卖出价：每股 $BP_i$ 元。
• 买入限额：当天至多只能买入 $AS_i$ 股。
• 卖出限额：当天至多只能卖出 $BS_i$ 股。

为了维护市场的稳定和防止垄断，股票交易所制定了以下两条严格的规定：

1. 持仓上限：在任何时刻，Y 同学持有的股票总数不能超过 $\text{MaxP}$ 股。
2. 交易冷却期：两次交易之间至少需要间隔 $W$ 天。具体来说，如果在第 $i$ 天进行了交易（无论是买入还是卖出），那么从第 $i+1$ 天到第 $i+W$ 天（共 $W$ 天）都不能进行任何交易。下一次最早能进行交易的时间是第 $i+W+1$ 天。

在第 $1$ 天之前，Y 同学持有无限的本金，但没有持有任何股票。 Y 同学希望在第 $T$ 天结束时，通过合理的交易策略，赚取最多的钱（即最终持有的现金减去初始本金的最大值）。请你帮助他计算这个最大收益。

输入格式

第一行包含三个整数 $T$，$\text{MaxP}$ 和 $W$，分别表示天数、最大持仓量和冷却期天数。

接下来 $T$ 行，第 $i$ 行（$1 \le i \le T$）包含四个整数 $AP_i, BP_i, AS_i, BS_i$，描述第 $i$ 天的股票行情。

输出格式

输出一行一个整数，表示 Y 同学在 $T$ 天后能获得的最大利润。

样例

样例输入 #1

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

样例输出 #1

3

数据范围与约定

对于 $100\%$ 的数据，保证：

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