/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君はイベント企画会社を経営しており、N 件のイベント開催依頼を受けている。依頼には 1 から N までの番号が付けられており、依頼 i（1 \leq i \leq N）には、会場の使用開始時刻 L_i、使用終了時刻 R_i、および報酬 V_i が設定されている。ここで時刻は整数で表される。
高橋君が利用できる会場は 1 つだけであり、同じ時間帯に複数のイベントを開催することはできない。依頼 i を実行すると、半開区間 [L_i, R_i) で表される時間帯（時刻 L_i 以上 R_i 未満）の間、会場を占有する。依頼 i と依頼 j（i \neq j）が両立するとは、占有する時間帯が重ならないこと、すなわち R_i \leq L_j または R_j \leq L_i が成り立つことをいう。特に、一方の終了時刻と他方の開始時刻が一致する場合（例えば R_i = L_j）は両立する。
一方、ライバル会社の青木君は、高橋君の利益を最小化するために妨害工作を行う。青木君は、N 件の依頼のうちちょうど K 件を選んでキャンセルさせる（キャンセルする K 件は互いに異なる依頼でなければならない）。青木君は、高橋君がキャンセル後に最適に行動することを見越した上で、高橋君が最終的に得られる報酬の合計が最小となるようにキャンセルする K 件を選ぶ。
キャンセルされずに残った N - K 件の依頼の中から、高橋君はどの 2 つも両立するように 0 件以上の依頼を選んで実行し、報酬の合計を最大化する。各依頼は最大 1 回しか実行できない。0 件を選んだ場合、報酬の合計は 0 である。
青木君が最適にキャンセルを行い、その後高橋君が残った依頼から最適に選んだとき、高橋君が得られる報酬の合計を求めよ。
制約
- 1 \leq N \leq 8
- 0 \leq K \leq N
- 0 \leq L_i < R_i \leq 100
- 1 \leq V_i \leq 1000
- 入力はすべて整数である
入力
N K L_1 R_1 V_1 L_2 R_2 V_2 \vdots L_N R_N V_N
- 1 行目には、依頼の件数 N と、青木君がキャンセルさせる件数 K が、スペース区切りで与えられる。
- 続く N 行のうち i 行目（1 \leq i \leq N）には、依頼 i の使用開始時刻 L_i、使用終了時刻 R_i、報酬 V_i がスペース区切りで与えられる。
出力
青木君が最適にキャンセルを行い、その後高橋君が最適に依頼を選んだときの、高橋君が得られる報酬の合計を 1 行で出力せよ。
入力例 1
3 1 0 2 5 2 4 3 0 3 10
出力例 1
8
入力例 2
4 2 0 5 100 5 10 100 0 10 50 3 7 50
出力例 2
50
入力例 3
6 2 0 3 10 3 6 20 6 9 10 1 5 25 4 8 15 0 9 30
出力例 3
30
入力例 4
8 3 0 10 50 10 20 60 20 30 70 0 15 100 15 30 90 5 25 80 0 30 200 12 18 40
出力例 4
110
入力例 5
1 1 0 100 1000
出力例 5
0
Score : 400 pts
Problem Statement
Takahashi runs an event planning company and has received N event requests. The requests are numbered from 1 to N, and request i (1 \leq i \leq N) specifies a venue start time L_i, end time R_i, and reward V_i. Times are represented as integers.
Takahashi has access to only one venue and cannot hold multiple events during the same time period. Executing request i occupies the venue during the time period represented by the half-open interval [L_i, R_i) (from time L_i inclusive to time R_i exclusive). Requests i and j (i \neq j) are said to be compatible if their occupied time periods do not overlap, that is, if R_i \leq L_j or R_j \leq L_i holds. In particular, if one's end time equals the other's start time (e.g., R_i = L_j), they are compatible.
Meanwhile, his rival Aoki will carry out sabotage to minimize Takahashi's profit. Aoki selects exactly K of the N requests to cancel (the K cancelled requests must all be distinct). Aoki chooses which K requests to cancel so as to minimize the total reward Takahashi can ultimately obtain, anticipating that Takahashi will act optimally after the cancellation.
From the remaining N - K requests that were not cancelled, Takahashi selects 0 or more requests to execute such that every pair of selected requests is compatible, maximizing the total reward. Each request can be executed at most once. If 0 requests are selected, the total reward is 0.
Determine the total reward Takahashi obtains when Aoki cancels optimally and then Takahashi selects optimally from the remaining requests.
Constraints
- 1 \leq N \leq 8
- 0 \leq K \leq N
- 0 \leq L_i < R_i \leq 100
- 1 \leq V_i \leq 1000
- All input values are integers
Input
N K L_1 R_1 V_1 L_2 R_2 V_2 \vdots L_N R_N V_N
- The first line contains the number of requests N and the number of requests K that Aoki will cancel, separated by a space.
- The following N lines each describe a request: the i-th line (1 \leq i \leq N) contains the start time L_i, end time R_i, and reward V_i of request i, separated by spaces.
Output
Output in a single line the total reward Takahashi obtains when Aoki cancels optimally and then Takahashi selects optimally from the remaining requests.
Sample Input 1
3 1 0 2 5 2 4 3 0 3 10
Sample Output 1
8
Sample Input 2
4 2 0 5 100 5 10 100 0 10 50 3 7 50
Sample Output 2
50
Sample Input 3
6 2 0 3 10 3 6 20 6 9 10 1 5 25 4 8 15 0 9 30
Sample Output 3
30
Sample Input 4
8 3 0 10 50 10 20 60 20 30 70 0 15 100 15 30 90 5 25 80 0 30 200 12 18 40
Sample Output 4
110
Sample Input 5
1 1 0 100 1000
Sample Output 5
0