Hero Leveling (Problem H, CS3233 Midterm Contest 2024, 2024)
Time limit: 2 sec
Memory limit: 1024 MB

# Problem Statement
Edgar wants to be a hero! However, to take the Hero Qualification Test, he must be at least level $L$. He is currently level $0$, and there are $N$ quests available for him to take. Quest $i$ requires him to be at least level $M_i$ to complete, and he will gain $X_i$ levels upon completing the quest. Each quest can only be done at most once. Additionally, due to the nature of these quests, quest $i$ has a trauma level $T_i$ associated with it.

Luckily, Edgar has poor memory so he will only remember the $K$ most traumatic quests he has done! His _trauma rating_ is therefore the sum of the $K$ largest trauma values among the quests he has done. If he does less than $K$ quests, then his trauma rating is just the sum of the trauma level of all quests he has done.

Help Edgar determine what is the minimum trauma rating he needs to reach at least level $L$ and take the Hero Qualification Test!

# Input

The first line of input consists of a three positive integers $N$, $K$, $L$, the number of quests, the maximum number of trauma levels he can remember, and the minimum level he needs to reach  
$(1 \le N \le 150,\ 1 \le K \le N,\ 1 \le L \le 1.5 \cdot 10^{11})$.

The following $N$ lines each contain three positive integers $M_i, X_i, T_i$, the minimum level Edgar needs to be to do quest $i$, the number of levels he gains from doing it, and the trauma level of the quest  
$(0 \le M_i \le 1.5 \cdot 10^{11},\ 1 \le X_i \le 10^9,\ 1 \le T_i \le 150)$.

**Additional Constraint**: It is guaranteed that Edgar will be able to reach level $L$ with the quests given.

# Output

Output a single integer, the minimum trauma rating Edgar needs to reach at least level $L$.

# Sample Input #1
```
5 2 10
0 3 5
5 5 9
2 2 3
7 4 6
0 4 7
```
# Sample Output #1
```
13
```
# Sample Input #2
```
6 4 10
3 6 6
0 4 7
0 3 5
4 2 4
6 7 4
7 3 3
```
# Sample Output #2
```
13
```

Sample inputs:
5 2 10
0 3 5
5 5 9
2 2 3
7 4 6
0 4 7

6 4 10
3 6 6
0 4 7
0 3 5
4 2 4
6 7 4
7 3 3

Sample outputs:
13

13

# Solution Analysis

Firstly, note that a set of quests can be completed if and only if it can be completed when we do the quests in increasing order of their $m_i$. Thus we will sort the quests by their $m_i$ value. We shall also interchangeably use the terms "trauma rating" and "cost".

We first discuss an initial idea, that gives us a polynomial time solution at least.

If the optimal solution uses at most $K$ quests, then we can run a solution that takes the trauma rating as the sum of all quests done rather than just the $K$ largest. Let $dp[i][j][k]$ be the highest level we can reach using the first $i$ quests, if the sum of their trauma levels is $j$, and we have done exactly $k$ quests. The answer is then the minimum $j$ such that there exists $k$ with $dp[n][j][k] \ge M$.

Now note that if we do more than $K$ quests, then everything after the $K$-th highest trauma level is basically free. Hence let’s set a cutoff level for where the quests start being free, and we want to do **exactly $K$** non-free quests.

We iterate on $c = 1, \ldots, N$, and let the $c$ quests with the smallest trauma level be free (set $T_i = 0$). Now we just run a very similar DP to the above: let $dp[i][j][k]$ be the highest level we can reach using the first $i$ quests, if the sum of their trauma levels is $j$, and we have done exactly $k$ non-free quests. We update the answer with the minimum $j$ such that $dp[n][j][K] \ge M$, for each $c$. This solution runs in $\mathcal{O}(N^4 \cdot \max(T_i))$, which is too slow.

We try to optimise this by removing the last dimension in the DP state. In other words, we try to find a way that lets us not keep track of exactly how many free quests we have done. Note that if we use more than $K$ free things, we get a suboptimal answer, so we just need to deal with the case when we use less than $K$ free quests.

If we do less than $K$ free quests, then we are ignoring the fact that we’ve treated cheaper quests as free. So when we make the $c$ quests with smallest costs be free, let $C$ be the $c$-th smallest cost. We will assume we have already incurred an initial cost of $K \cdot C$, and now we replace all $c_i$ by $\max(0, c_i - C)$.

Now we define $dp[i][j]$ as the highest level we can reach using only the first $i$ quests, such that the sum of their transformed costs is $j$. We can update the answer with $\min(\text{ans}, K \cdot C + j)$, where $j$ is the minimum number such that $dp[i][j] \ge M$. This solution runs in $\mathcal{O}(N^3 \cdot \max(T_i))$ time, which is sufficiently fast.

Why this solution works is left as a simple exercise to the readers.


Special judge (C++ scorer):