← 返回题目列表

AtCoder · awc0095_d

D. 活动场地预订

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥经营一家活动策划公司,并已收到 N 事件请求。请求编号从 1 to N,并请求 i (1 \leq i \leq N) 指定场地开始时间 L_i,结束时间 R_i,并奖励 V_i。时间以整数表示。

高桥只能进入一个场地,并且不能在同一时间段内举办多个活动。执行请求 i 在半开区间代表的时间段内占用场地 [L_i, R_i) (从时间 L_i 包括时间 R_i 独家)。要求 i 和 j (i \neq j)据说是 兼容 如果它们占用的时间段不重叠,即如果 R_i \leq L_j or R_j \leq L_i 成立。特别是,如果一个人的结束时间等于另一个人的开始时间(例如, R_i = L_j),它们是兼容的。

与此同时,他的竞争对手青木将进行破坏活动,以尽量减少高桥的利润。青木精选 正是 K 的 N 请求取消( K 取消的请求必须全部不同)。青木选择哪个 K 请求取消,以尽量减少高桥最终可以获得的总奖励,并预计高桥在取消后会采取最佳行动。

从剩余的 N - K 未取消的请求,高桥选择 0 或更多要执行的请求,使得每对选定的请求都是兼容的,从而最大化总奖励。每个请求最多可以执行一次。如果 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
  • 第一行包含请求数 N 和请求数量 K 青木将取消,以空格分隔。
  • 以下 N 行每行描述一个请求: i- 第行 (1 \leq i \leq N) 包含开始时间 请求的 L_i,结束时间 R_i,并奖励 V_i 请求的 i,用空格分隔。

输出

单行输出青木最优取消时高桥获得的总奖励,然后高桥从剩余请求中进行最优选择。


示例输入 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