「Atcoder ABC 015D 高橋君の苦悩」動的計画法のDPテーブル作り方について質問

前提・実現したいこと

「Atcodr Beginner Contest 015 D 高橋君の苦悩」について考えたコードの間違いを確認したい

https://atcoder.jp/contests/abc015/tasks/abc015_4

発生している問題・エラーメッセージ

テストケース36/47は正解しており、11問不正解。

該当のソースコード

python
1W = int(input())
2N,K = map(int,input().split())
3ab = [list(map(int,input().split())) for _ in range(N)]
4
5dp = [[0]*(W+1) for _ in range(N+1)]
6cnt= [[0]*(W+1) for _ in range(N+1)]
7
8for i in range(N):
9    a,b = ab[i]
10    for j in range(W+1):
11        if j-a<0:
12            dp[i+1][j] = dp[i][j]
13            cnt[i+1][j] = cnt[i][j]
14        else:
15            if dp[i][j]<dp[i][j-a]+b:
16                cnt[i+1][j] = cnt[i][j-a]+1
17                dp[i+1][j] = dp[i][j-a]+b
18            else:
19                cnt[i+1][j] = cnt[i][j]
20                dp[i+1][j] = dp[i][j]
21
22ans = 0
23for i in range(W+1):
24    if cnt[N][i]<=K:
25        ans = dp[N][i]
26print(ans)

試したこと

最近動的計画法を学んでいるんですが、よく出てくる2次元のDPテーブルを使ってできないかと問題に挑みました。制約に対する変数が多いため、２次元DPテーブル１つではだめだと思い、スクリーンショットの個数についてメインのDPテーブル(変数名：dp)と別に、cntという変数名でDPテーブルを作成して、数えたらうまい行かないかと考えてみました。サンプルケースは問題なく通過し、うまくテーブルも更新されているように見えたため考え方としていけるのかな、と思いましたがテストケースWAになってしまいした。考え方が間違っているのでしょうか。宜しくお願い致します。