行う仕事の集合を決めたとき、それらは締切の早い順に行うとしてよいです（そうでない箇所があれば入れ替えて損をしない）。
よって、全ての仕事を締め切りの昇順にソートしたのち、行う仕事としてその部分列を決める問題とみなしてよいです。

\(\mathrm{dp}[i][k][t]\) を「 \(i\) 番目までの仕事のうち \(t\) 日目までに \(k\) 個を完了したときの報酬（ボーナス除く）の最大値（不可能なら \(-\infty\)）」とします。 このとき配るDPを考えると、 \(i+1\) 番目の仕事をするかしないかにより

• \(\mathrm{dp}[i+1][k][t] \xleftarrow{\text{chmax}} \mathrm{dp}[i][k][t]\)
• \(t+D_{i+1}\leq T_{i+1}\) のとき \(\mathrm{dp}[i+1][k+1][t+D_{i+1}] \xleftarrow{\text{chmax}} \mathrm{dp}[i][k][t]+V_{i+1}\)

という 2 つの遷移が得られます。よって \(O(N^2M)\) 時間でこのDPテーブルを埋めることができます。その後、元の問題の答えを得ることは容易です。

以下の実装例では DP テーブルを \(i\) に関して in-place に更新することで、空間計算量を \(O(NM)\) としています。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n,m,K,b;
  cin >> n >> m >> K >> b;
  vector<array<int,3>> data(n);
  for(int i=0; i<n; i++) cin >> data[i][1] >> data[i][2] >> data[i][0];
  sort(data.begin(), data.end());

  vector<vector<long long>> dp(n+1, vector<long long>(m+1, -1e18));
  dp[0][0] = 0
  for(int i=0; i<n; i++){
    auto[T, D, V] = data[i];
    for(int k=i; k>=0; k--){
      for(int t=0; t<=T-D; t++){
        dp[k+1][t+D] = max(dp[k+1][t+D], dp[k][t] + V)
      }
    }
  }

  long long ans = 0;
  for(int k=0; k<=n; k++){
    for(int t=0; t<=m; t++){
      ans = max(ans, dp[k][t] + (k>=K?b:0));
    }
  }
  cout << ans << endl;
}

実装例 (Python)

N, M, K, B = map(int, input().split())
data = []
for _ in range(N):
  D, V, T = map(int, input().split())
  data.append((T, D, V))
data.sort()

dp=[[-10**18]*(M+1) for _ in range(N+1)]
dp[0][0] = 0
for i, (T, D, V) in enumerate(data):
  for k in range(i, -1, -1):
    for t in range(T-D+1):
      dp[k+1][t+D] = max(dp[k+1][t+D], dp[k][t] + V)

ans = 0
for k in range(N+1):
  ans = max(ans, max(dp[k]) + (B if k>=K else 0))

print(ans)