807 . 租房子
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
1 3 5
4 7 8
2 5 9
6 9 7
Sample Output 1
16 2
4 3
4 3
Sample Input 2
3
2 3 4
4 5 7
1 9 15
2 3 4
4 5 7
1 9 15
Sample Output 2
15 1
3
3
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~15 | 無額外限制 | 100 |