\(d[i][j]\) を「部屋 \(i\) にいて、今荷物をちょうど \(j\) 個持っている時の報酬の合計の最大値」と定義します。

初期値は \(d[0][0]=0,d[0][j]=-\infty\) \((j > 0)\) です。

遷移は \(T_i=1\) なら \(d[i][j]=\max(d[i-1][j],d[i-1][j-1]+A_i)\)、\(T_i=0\) なら \(j=0\) の場合は \(d[i][0]=\max(d[i-1][0]+A_i,d[i-1][1]+A_i)\) 、\(j>0\) の場合は \(d[i][j]=\max(d[i-1][j],d[i-1][j+1]+A_i)\) です。

実装例(Python3)

n, k = map(int, input().split())
INF = 10**18
d = [-INF] * (k + 1)
d[0] = 0
for _ in range(n):
    t, a = map(int, input().split())
    if t:
        for i in range(k, 0, -1):
            d[i] = max(d[i], d[i - 1] + a)
    else:
        d[0] += a
        for i in range(k):
            d[i] = max(d[i], d[i + 1] + a)
print(d[0])