原題來自：SCOI 2010
最近 lxhgww 又迷上了投資股票，通過一段時間的觀察和學(xué)習(xí)，他總結(jié)出了股票行情的一些規(guī)律。
通過一段時間的觀察，lxhgww 預(yù)測到了未來 $T$ 天內(nèi)某只股票的走勢，第 $i$ 天的股票買入價為每股 $AP_iA$ ，第 $i$ 天的股票賣出價為每股 $BP_i$ （數(shù)據(jù)保證對于每個 $i$，都有 $AP_i\\ge BP_i$ ），但是每天不能無限制地交易，于是股票交易所規(guī)定第 $i$ 天的一次買入至多只能購買 $AS_i$ 股，一次賣出至多只能賣出 $BS_i$ 股。
另外，股票交易所還制定了兩個規(guī)定。為了避免大家瘋狂交易，股票交易所規(guī)定在兩次交易（某一天的買入或者賣出均算是一次交易）之間，至少要間隔 $W$ 天，也就是說如果在第 $i$ 天發(fā)生了交易，那么從第 $i+1$ 天到第 $i+W$ 天，均不能發(fā)生交易。同時，為了避免壟斷，股票交易所還規(guī)定在任何時間，一個人的手里的股票數(shù)不能超過 $MaxP$。
在第一天之前，lxhgww 手里有一大筆錢（可以認(rèn)為錢的數(shù)目無限），但是沒有任何股票，當(dāng)然，$T$ 天以后，lxhgww 想要賺到最多的錢，聰明的程序員們，你們能幫助他嗎？

輸入數(shù)據(jù)第一行包括三個整數(shù)，分別是 $T$,$MaxP$,$W$。
接下來 $T$ 行，第 $i$ 行代表第 $i-1$ 天的股票走勢，每行四個整數(shù)，分別表示 $AP_i,BP_i,AS_i,BS_i$ 。

輸出數(shù)據(jù)為一行，包括一個數(shù)字，表示 lxhgww 能賺到的最多的錢數(shù)。

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

3