TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

100.0% (3/3)

Tags

Description

IOICamp 是一個由臺大資工學生所舉辦的程式解題競賽集訓營,而小風是一位充滿著熱忱的營隊工作人員,他知道接下來會收到來自營隊總召波路特石的 N 項任務,第 i 項任務包括:

  • 開始日期 si,代表這項任務在第 si 天後便可以被執行。
  • 截止日期 ei,代表這項任務在第 ei+1 天後便不能再執行(也就是說,小風只能在第 siei 天執行第 i 項任務)。
  • xi 單位的工作,每一單位的工作都需要花費小風一天的時間完成。

由於小風是時間控管大師,他每一天可以隨意選擇任意一項任務的其中一單位工作執行(當然,要在該項任務的可執行時間內),不過這一天他就只能專心執行這一項任務,不可以更改。

為了鼓勵小風盡可能的完成多一點任務,波路特石額外又給他了一些獎勵。對於第 i 個任務,波路特石設定了一個獎勵參數 pi,代表如果小風完成了 yi 單位第 i 項任務的工作,他可以獲得 piyi 塊錢,注意到即使小風沒有完成整項任務,他依然拿得到錢。

另外,由於總召的事情繁瑣,波路特石能定好任務細節的時間有限,已知他已經在心中挑選了至多隨意 30 天來處理小風的任務,因此,開始日期的種類至多只有 30

請幫助小風找出在最佳的執行任務時間分配下,他最多可以拿到多少錢。

Input Format

輸入首行有一個正整數 N,代表波路特石打算派給小風的任務數量。

接下來 N 行,每行四個正整數 si,ei,xi,pi,代表第 i 個任務的資訊。

  • 1N105
  • 1siei109
  • 1xieisi+1
  • 1pi109
  • si 的種類至多只有 30

Output Format

輸出一行一個整數,代表小風在最佳的執行任務時間分配下最多可以賺到多少錢。

Sample Input 1

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

Sample Output 1

4

Sample Input 2

5
6 7 2 6
1 10 3 6
6 8 2 8
3 8 1 9
1 9 7 2

Sample Output 2

55

Sample Input 3

5
9 10 1 5
5 15 6 7
4 6 2 8
1 6 1 3
3 9 1 1

Sample Output 3

67

Hints

Problem Source

IOICamp 2022 Day2 pB

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~19 N3000 40
3 0~38 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 524288 65536 1 2 3
1 5000 524288 65536 1 2 3
2 5000 524288 65536 1 2 3
3 5000 524288 65536 2 3
4 5000 524288 65536 2 3
5 5000 524288 65536 2 3
6 5000 524288 65536 2 3
7 5000 524288 65536 2 3
8 5000 524288 65536 2 3
9 5000 524288 65536 2 3
10 5000 524288 65536 2 3
11 5000 524288 65536 2 3
12 5000 524288 65536 2 3
13 5000 524288 65536 2 3
14 5000 524288 65536 2 3
15 5000 524288 65536 2 3
16 5000 524288 65536 2 3
17 5000 524288 65536 2 3
18 5000 524288 65536 2 3
19 5000 524288 65536 2 3
20 5000 524288 65536 3
21 5000 524288 65536 3
22 5000 524288 65536 3
23 5000 524288 65536 3
24 5000 524288 65536 3
25 5000 524288 65536 3
26 5000 524288 65536 3
27 5000 524288 65536 3
28 5000 524288 65536 3
29 5000 524288 65536 3
30 5000 524288 65536 3
31 5000 524288 65536 3
32 5000 524288 65536 3
33 5000 524288 65536 3
34 5000 524288 65536 3
35 5000 524288 65536 3
36 5000 524288 65536 3
37 5000 524288 65536 3
38 5000 524288 65536 3