[Scoi2010]股票交易

最近 lxhgww 迷上了股票投资。经过一段时间的观察和学习，他总结出了一些股票行情的规律，并预测了未来 $T$ 天内某只股票的走势。

第 $i$ 天，该股票的买入价为每股 $AP_i$ ，卖出价为每股 $BP_i$ 。数据保证对每个 $i$ ，均有 $AP_i\ge BP_i$ 。由于每天不能无限制地交易，股票交易所规定：第 $i$ 天一次买入至多购买 $AS_i$ 股，一次卖出至多卖出 $BS_i$ 股。

此外，股票交易所还制定了以下规定：

为了避免频繁交易，两次交易之间至少要间隔 $W$ 天。某一天进行买入或卖出均算作一次交易。也就是说，如果第 $i$ 天发生了交易，那么第 $i+1$ 天至第 $i+W$ 天均不能发生交易；
为了避免垄断，在任何时刻，一个人持有的股票数量都不能超过 $\mathrm{MaxP}$ 股。

在第 $1$ 天之前，lxhgww 拥有足够多的钱，可以认为资金无限，但没有持有任何股票。他希望在 $T$ 天后获得尽可能多的利润。请计算他最多能够赚到多少钱。

输入格式

第一行包含 $3$ 个整数 $T$ 、 $\mathrm{MaxP}$ 和 $W$ ，分别表示交易天数、最多能够持有的股票数量，以及两次交易之间至少需要间隔的天数。

接下来 $T$ 行，第 $i$ 行包含 $4$ 个整数 $AP_i$ 、 $BP_i$ 、 $AS_i$ 和 $BS_i$ ，分别表示第 $i$ 天每股股票的买入价、卖出价、一次至多能够买入的股票数量，以及一次至多能够卖出的股票数量。

输出一行一个整数，表示 lxhgww 最多能够赚到的钱数。

本题为 SCOI 2010 试题「股票交易」，题面与测试数据整理自 BZOJ 1855。