Одинаковый код на python и C++ работает по-разному

Код на C++ работает, а на python нет. В коде подобие задачи о рюкзаке с двумя параметрами Код на C++

typedef long long ll;
int main()
{
    ll s, k;
    cin >> s >> k;
    ll ans = INF;
    ll MAX_WEIGHT = s * 2;
    ll w[k+1], p[k+1], dp[k+1][MAX_WEIGHT];
    for (int i = 1; i <= k; i++)
    {
        cin >> w[i] >> p[i];
        if (w[i] >= s)
            ans = min(ans, p[i]);
    }
    for (ll i = 0; i <= k; i++)
        for (ll j = 0; j < MAX_WEIGHT; j++)
            dp[i][j] = INF;
    for (int i = 0; i <= k; i++)
        dp[i][0] = 0;
    for (ll i = 1; i <= k; i++)
        for (ll j = 1; j < MAX_WEIGHT; j++)
        {
            if (j >= w[i])
            {
                dp[i][j] = min(dp[i-1][j], dp[i-1][j - w[i]] + p[i]);
            }
            else
                dp[i][j] = dp[i-1][j];
        }
    for (ll i = 0; i <= k; i++)
        for (ll j = s; j < MAX_WEIGHT; j++)
            ans = min(ans, dp[i][j]);
    cout << ans;
}

Код на python:

B = [10**18] * 2500
B[0] = 0
A = [0] * 1100
for i in range(len(A)):
    A[i] = B
s, k = input().split()
s = int(s)
k = int(k)
w = [0] * (k + 2)
p = [0] * (k + 2)
ans = 10**18
for i in range(1, k+1):
    x, y = input().split()
    x = int(x)
    y = int(y)
    if x >= s:
        ans = min(ans, y)
    w[i] = x
    p[i] = y
for i in range(1, k + 1):
    for j in range(1, 2500):
        if j >= w[i]:
            A[i][j] = min(A[i-1][j], A[i-1][j - w[i]] + p[i])
        else:
            A[i][j] = A[i-1][j]
for i in range(k+1):
    for j in range(s, 2500):
        ans = min(ans, A[i][j])
print(ans)

Мне кажется, что проблема в этом куске кода

for i in range(1, k + 1):
    for j in range(1, 2500):
        if j >= w[i]:
            A[i][j] = min(A[i-1][j], A[i-1][j - w[i]] + p[i])
        else:
            A[i][j] = A[i-1][j]

Пример теста:

22 8
6 15
6 17
4 18
3 48
3 48
2 24
3 11
3 16
Правильный ответ 77