TopCoder

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

66.7% (6/9)

Tags

Description

你是一個房東,並有 N 個人向你提出租約。其中第 i 個人想從第 ui 天租到第 vi 天,並願意支付 wi 元。你想要選出一些人接受他們的租約。對於每筆租約,你只能全部接受或全部拒絕而不能部分接受,且同一天不能租給兩個不同人。請回答在適當選擇下,你能創造的最高收入是多少?

Input Format

輸入第一行是一個整數 N,代表租約筆數。
接下來 N 行每行三個空白分隔的正整數 ui,vi,wi(1iN),分別代表起始時間,結束時間和願意付的租金。

輸入保證 1N1031ui,vi,wi104。請注意輸入沒有保證兩個租約不會有完全相同的時間區間。

Output Format

輸出包含最大的收入和列出一種方案。

請輸出兩行,第一行是兩個空白分隔的正整數 W,M,代表最多可以獲得的收入是 W 以及存在一種方法可以用 M 筆租約達成。第二行是 M 個空白分隔的正整數,代表要選哪些筆訂單,訂單編號 1N,輸出可以按照任意順序。

Sample Input 1

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

Sample Output 1

16 2
4 3

Sample Input 2

3
2 3 4
4 5 7
1 9 15

Sample Output 2

15 1
3

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~15 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2