1921 . 吐鈔機2
TopCoder
Tags
Description
有一天你透過某種神秘力量找到了黑魔法地下市場。你赫然發現在這個市場上竟然有大量的吐鈔機在流通，所以你打算做個好計畫，準備在接下來的$D+1$天內大賺一筆。
這個黑魔法地下市場的吐鈔機販賣部，在09:00-10:00會提供收購二手吐鈔機的服務，而19:00-20:00則提供販賣新吐鈔機的服務。
你透過強大的黑魔法力量得知了接下來將會販賣的新吐鈔機資訊。對於第$i$種吐鈔機，它只要在某一天有任何一個時間開著，它這天就會吐出$G_i$元的鈔票。而它會在第$D_i$天以$P_i$元的價格販賣，由於吐鈔機的生意都很好，過了這一天之後就再也買不到這種吐鈔機了。魔法世界裡是沒有銀行的，所以你絕對沒辦法跟別人貸款，自己有多少錢就只能買多少錢的吐鈔機。
當然，你也調查了二手市場的行情，得知第$i$種吐鈔機的二手轉售價格是$R_i$。當然，二手收購價一定比原價還要低。
然而，吐鈔機的運作有幾個限制：吐鈔機只能在10:00-19:00期間運作，而且一個人在一個時刻只能擁有一臺吐鈔機，否則黑魔法力量會互相干擾，把所有的錢全部變成廢紙。
你在第1天09:00的時候有$C$元本金，接下來只能靠吐鈔機賺錢。求在第$D+1$天10:00的時候，你最多可以擁有多少錢。
Input Format
第一行有三個正整數$N,C,D$，分別代表吐鈔機的種類數、你一開始擁有的本金和你打算在這個市場裡交易多久。
接下來$N$行，每行有四個正整數$D_i, P_i, R_i, G_i$，代表第$i$臺吐鈔機的資訊。關於它們的意義，請參照題敘。
因為這是個魔法題，為了順利作答，你可能會需要用到__int128的黑魔法。這是範圍在$[-2^ {127},2^ {127})$的整數型別，由g++提供。使用這個型別不需要引入任何標頭檔。這個型別不能直接cin/cout/printf/scanf，但是可以轉型成一般的整數型別。
當然，並不一定必須用到這個黑魔法才能解開這個魔法題。
對於所有的測資，$N\leq 10^ 5$；$C,D,G_i\leq 10^ 9$；$D_i\leq D$；$R_i<P_i\leq 10^ 9$。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~7) | $N\leq 20$ | 9 |
| 2 (0~9) | $N\leq 300$ | 12 |
| 3 (0~12) | $N\leq 1000$ | 13 |
| 4 (0~15) | $N\leq 10^ 4$ | 25 |
| 5 (0~19) | 無 | 41 |
Output Format
輸出一行包含一個正整數，代表在第$D+1$天10:00的時候，你最多可以擁有多少錢。
Sample Input 1
6 10 20 6 12 1 3 1 9 1 2 3 2 1 2 8 20 5 4 4 11 7 4 2 10 9 1
Sample Output 1
44
Hints
對於範例測資：
在第3天的時候買進第3種吐鈔機，此時剩8元；
在第6天的時候賣掉，此時有13元；買進第1種吐鈔機，剩1元；
到第21天的時候賣掉，總共得到44元。
Problem Source
建國中學105學年度校內第五次模擬賽pD
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~7 | 9 |
| 2 | 0~9 | 12 |
| 3 | 0~12 | 13 |
| 4 | 0~15 | 25 |
| 5 | 0~19 | 41 |