ちょうど \(K\) 日間収穫するのではなく、収穫する日数を \(K\) 日以下としても本問題の答えは変わりません。

また、この緩和した条件下では得られる果物の美味しさを \(\max(0,A_i-(t-1)D_i)\) ではなく \(A_i-(t-1)D_i\) としても答えは変わりません。したがって、以下では \(K\) 日以下・美味しさが \(A_i-(t-1)D_i\) とした問題を考えます。

収穫する木の集合を固定たとき、その中では \(D_i\) が大きい果物から順番に収穫していくことが最適であることが分かります。

したがって、各木を \(D\) の大きい順にソートして \(d[i][j]\) を「木 \(1\) から木 \(i\) までからちょうど \(j\) 日収穫したときの、美味しさの総和」とした時の \(\displaystyle \max_{0\le j\le K} d[N][j]\) が答えになります。

この DP の遷移は \(O(1)\) 時間で可能なので、全体として \(O(NK)\) 時間でこの問題に正答することができます。

実装例(Python3)

n, k = map(int, input().split())
ad = [tuple(map(int, input().split())) for _ in range(n)]
ad.sort(key=lambda x: -x[1])
dp = [0] + [-10**18] * k
for a, d in ad:
    for i in range(k - 1, -1, -1):
        dp[i + 1] = max(dp[i + 1], dp[i] + a - i * d)
print(max(dp))