青木君がキャンセルするような \(K\) 件を全探索します。全探索は bit 演算子を使うことで効率的に行えますが、この問題の制約下では愚直に bit 全探索を行なっても良いです。

あるキャンセルする \(K\) 件を選び、残りの \(N-K\) 件の中で高橋君が最大化した場合の最大値を求める方法を考えます。

この制約下ではこの最大値も高橋君が最終的に選ぶ依頼を全探索することで計算することができます。

以上を適切に実装することでこの問題に正答することができます。

以下の実装例では愚直な全探索から少しだけ工夫をしています。具体的には、\(d[S]\) を「依頼集合 \(S\) の中から日時が被らないようにいくつか選んだ場合の報酬の合計の最大値」として \(O(N2^N)\) 時間で計算し、青木君側の全探索ではこの \(d\) を用いることで全体で \(O(N2^N)\) 時間で計算しています。

実装例(Python3)

n, k = map(int, input().split())
l = [-1] * n
r = [-1] * n
v = [-1] * n
for i in range(n):
    l[i], r[i], v[i] = map(int, input().split())
nn = 1 << n
d = [0] * nn
for bi in range(nn):
    sum_v = 0
    lr = []
    for i in range(n):
        if (bi >> i) & 1:
            lr.append((l[i], r[i]))
            sum_v += v[i]
    lr.sort()
    ok = True
    for i in range(len(lr) - 1):
        ok &= lr[i][1] <= lr[i + 1][0]
    if ok:
        d[bi] = sum_v
for bi in range(nn):
    for i in range(n):
        bbi = bi | (1 << i)
        d[bbi] = max(d[bbi], d[bi])
p = [0] * nn
for i in range(1, nn):
    p[i] = p[i // 2] + i % 2
ans = 10**9
for bi in range(nn):
    if p[bi] != n - k:
        continue
    ans = min(ans, d[bi])
print(ans)