TopCoder

User's AC Ratio

95.5% (21/22)

Submission's AC Ratio

18.7% (64/342)

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

No. Testdata Range Score
1 0~7 9
2 0~9 12
3 0~12 13
4 0~15 25
5 0~19 41

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1 2 3 4 5
1 900 65536 262144 1 2 3 4 5
2 900 65536 262144 1 2 3 4 5
3 900 65536 262144 1 2 3 4 5
4 900 65536 262144 1 2 3 4 5
5 900 65536 262144 1 2 3 4 5
6 900 65536 262144 1 2 3 4 5
7 900 65536 262144 1 2 3 4 5
8 900 65536 262144 2 3 4 5
9 900 65536 262144 2 3 4 5
10 900 65536 262144 3 4 5
11 900 65536 262144 3 4 5
12 900 65536 262144 3 4 5
13 900 65536 262144 4 5
14 900 65536 262144 4 5
15 900 65536 262144 4 5
16 400 65536 262144 5
17 400 65536 262144 5
18 400 65536 262144 5
19 400 65536 262144 5