The Grand Endeavor

The first line of input contains two space-separated integers, 'N' and 'K'.

The next 'N' lines each contain three space-separated integers: duration, deadline, and reward for a single project.

Print a single integer representing the maximum total reward you can achieve.

A key insight for scheduling problems is to consider processing jobs in order of their deadlines. This greedy choice often simplifies the problem.
When a helper is used on a project with duration d, the new duration becomes floor(d / 2).
This problem can be solved using dynamic programming. A state could be defined by the projects considered, the time elapsed, and the number of helpers used.

Sample Input 1:

3 1
10 15 100
8 12 120
6 6 80

Sample Output 1:

220

Explanation for Sample 1:

There are 3 projects and 1 helper. Let's label them P1, P2, P3.
P1: {d:10, dl:15, r:100}
P2: {d:8, dl:12, r:120}
P3: {d:6, dl:6, r:80}

The optimal strategy is to perform the projects in increasing order of their deadlines: P3, then P2.

Attempt 1 (No helper):
- Start P3 at time 0. Finishes at 6 (deadline 6, OK). Reward: 80.
- Start P2 at time 6. Finishes at 6 + 8 = 14 (deadline 12, LATE). No reward.
- Total Reward: 80.

Attempt 2 (Use helper on P2):
- The duration of P2 becomes `floor(8 / 2) = 4`.
- Start P3 at time 0. Finishes at 6 (deadline 6, OK). Reward: 80.
- Start P2 (with helper) at time 6. Finishes at 6 + 4 = 10 (deadline 12, OK). Reward: 120.
- We don't have time for P1.
- Total Reward: 80 + 120 = 200.

Attempt 3 (Skip P3, Do P2 with helper and P1):
- Order P2, then P1. Use helper on P2.
- Start P2 (with helper) at time 0. Finishes at 4 (deadline 12, OK). Reward: 120.
- Start P1 at time 4. Finishes at 4 + 10 = 14 (deadline 15, OK). Reward: 100.
- Total Reward: 120 + 100 = 220. This is the maximum.

Sample Input 2:

2 1
10 10 100
10 20 120

Sample Output 2:

220

Explanation for Sample 2:

P1: {d:10, dl:10, r:100}
P2: {d:10, dl:20, r:120}
Optimal order is P1 then P2.
- Start P1 at time 0. Finishes at 10 (deadline 10, OK). Reward: 100.
- Start P2 at time 10. Finishes at 10 + 10 = 20 (deadline 20, OK). Reward: 120.
No helper is needed. Total Reward: 220.

Expected Time Complexity:

The expected time complexity is O(N * MaxDeadline * K).

Constraints:

1 <= N <= 50
0 <= K <= 50
1 <= duration <= deadline <= 2000
1 <= reward <= 1000

Time limit: 1 sec