你是一個房東,並有 N 個人向你提出租約。其中第 i 個人想從第 ui 天租到第 vi 天,並願意支付 wi 元。你想要選出一些人接受他們的租約。對於每筆租約,你只能全部接受或全部拒絕而不能部分接受,且同一天不能租給兩個不同人。請回答在適當選擇下,你能創造的最高收入是多少?
輸入第一行是一個整數 N,代表租約筆數。 接下來 N 行每行三個空白分隔的正整數 ui,vi,wi(1≤i≤N),分別代表起始時間,結束時間和願意付的租金。
輸入保證 1≤N≤103,1≤ui,vi,wi≤104。請注意輸入沒有保證兩個租約不會有完全相同的時間區間。
輸出包含最大的收入和列出一種方案。
請輸出兩行,第一行是兩個空白分隔的正整數 W,M,代表最多可以獲得的收入是 W 以及存在一種方法可以用 M 筆租約達成。第二行是 M 個空白分隔的正整數,代表要選哪些筆訂單,訂單編號 1∼N,輸出可以按照任意順序。