まず展示品を出店先の会場番号により分類します。

各会場 \(i\) に対し、\(\text{dp}_i[w]\) を「その会場の展示品で重さの合計 \(w\) 以下で得られる見込み利益の合計の最大値」とした DP を前計算します。

\(\text{d}[i][j][k]\) を「会場 \(1\) から会場 \(i\) まででちょうど \(j\) 個の会場に対して荷物を運び、それらの重さが合計 \(k\) であるような場合の得られる見込み利益の合計の最大値」とした DP を考えます。この DP は先ほど前計算した DP を元に効率よく計算することができます。

これらを元に、求める答えは \(\displaystyle \max_j (\text{d}[N][j][W]-j^2)\) と計算することができます。

計算量は \(O(NW+K^2W^2)\) です。工夫することで \(O(NKW)\) に改善することもできます。

実装例(Python3)

n, k, W = map(int, input().split())
g = [[] for _ in range(k)]
for _ in range(n):
    w, v, d = map(int, input().split())
    g[d - 1].append((w, v))
d = [[0] * (W + 1)]
for gg in g:
    if not gg:
        continue
    dp = [0] * (W + 1)
    for w, v in gg:
        for i in range(W, w - 1, -1):
            dp[i] = max(dp[i], dp[i - w] + v)
    dd = [a[:] for a in d]
    dd.append([0] * (W + 1))
    for i in range(len(d)):
        for j1 in range(W + 1):
            for j2 in range(W - j1 + 1):
                dd[i + 1][j1 + j2] = max(dd[i + 1][j1 + j2], d[i][j1] + dp[j2])
    d = dd
ans = max(d[i][W] - i * i for i in range(len(d)))
print(ans)