TopCoder

M0use

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

62.5% (5/8)

Description

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

Input Format

輸入第一行是一個整數 $N$，代表租約筆數。
接下來 $N$ 行每行三個空白分隔的正整數 $u_i, v_i, w_i (1\le i\le N)$，分別代表起始時間，結束時間和願意付的租金。

輸入保證 $1\le N\le 10^ 3$，$1\le u_i, v_i, w_i\le 10^ 4$。請注意輸入沒有保證兩個租約不會有完全相同的時間區間。

Output Format

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

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

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

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

807 . 租房子