TopCoder

User's AC Ratio

93.8% (15/16)

Submission's AC Ratio

16.6% (44/265)

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

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

44

Hints

對於範例測資:
在第3天的時候買進第3種吐鈔機,此時剩8元;
在第6天的時候賣掉,此時有13元;買進第1種吐鈔機,剩1元;
到第21天的時候賣掉,總共得到44元。

Problem Source

建國中學105學年度校內第五次模擬賽pD

Subtasks

For Testdata: 0 ~ 7, Score: 9
For Testdata: 0 ~ 9, Score: 12
For Testdata: 0 ~ 12, Score: 13
For Testdata: 0 ~ 15, Score: 25
For Testdata: 0 ~ 19, Score: 41
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 900 65536 262144
1 900 65536 262144
2 900 65536 262144
3 900 65536 262144
4 900 65536 262144
5 900 65536 262144
6 900 65536 262144
7 900 65536 262144
8 900 65536 262144
9 900 65536 262144
10 900 65536 262144
11 900 65536 262144
12 900 65536 262144
13 900 65536 262144
14 900 65536 262144
15 900 65536 262144
16 400 65536 262144
17 400 65536 262144
18 400 65536 262144
19 400 65536 262144