\(dp[j][k]\) を、ここまでで費用を \(j\) 使い、末尾の連続区間の長さが \(k\) であるときの最大値とします。ただし、\(k=2\) は長さ \(2\) 以上をまとめて表します。

区画 \(i\) を選ばない場合、末尾の連続区間はなくなるので状態は \(0\) になります。

区画 \(i\) を選ぶ場合は、

• \(k=0\) からは \(D_i\) を加えて状態 \(1\)
• \(k=1\) からは \(D_i+2B\) を加えて状態 \(2\)
• \(k=2\) からは \(D_i+B\) を加えて状態 \(2\)

へ遷移します。

これを費用が \(W\) 以下となる範囲で行えばよいです。

計算量は \(O(NW)\)、メモリ計算量は \(O(W)\) です。

実装例

n, w, b = map(int, input().split())

inf = 1 << 30
dp = [[-inf] * 3 for _ in range(w + 1)]
dp[0][0] = 0

for _ in range(n):
    d, c = map(int, input().split())
    ndp = [[-inf] * 3 for _ in range(w + 1)]

    for j in range(w + 1):
        ndp[j][0] = max(dp[j])

        if j + c <= w:
            ndp[j + c][1] = max(ndp[j + c][1], dp[j][0] + d)
            ndp[j + c][2] = max(ndp[j + c][2], dp[j][1] + d + 2 * b, dp[j][2] + d + b)
    dp = ndp

print(max(map(max, dp)))