複数の機械をまたぐ作業がないため、 \(1\) 台の機械で利益を最大化すればそれを \(M\) 台分行うことで利益を最大化できます。よって、以降は \(1\) 台の機械で利益を最大化してそれを \(M\) 倍したものを答えとします。

動的計画法 (DP) にて本問題を解くことを考えます。

\(dp[t]=\{\) \(t\) 分以下で得られる最大の利益 \(\}\) とします。

同じ製品を何度作っても同等の利益が得られるため、 \(x\) 分で \(y\) 円の利益が得られる製品が追加された時に以下のように DP テーブルを更新すればよいです。

• \(i=x,x+1,\dots,K\) について、この順に以下を繰り返す。
  • \(dp[i]=\max(dp[i],dp[i-x]+y)\) と更新する。

これで \(1\) 台の機械で \(K\) 分以下で得られる最大の利益が求められたため、本問題に正解することができます。
時間計算量は \(O(NK)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,M,K;
  cin >> N >> M >> K;
  vector<ll> dp(K+1,0);
  while(N--){
    ll C,T,P;
    cin >> C >> T >> P;
    P-=C;
    if(P>0){
      for(ll i=T;i<=K;i++){
        dp[i]=max(dp[i],dp[i-T]+P);
      }
    }
  }
  cout << M*dp[K] << "\n";
  return 0;
}