01背包

from collections import defaultdict

for _ in range(int(input())):
    m, x = map(int, input().split())
    c = [0] * (m + 1)
    h = [0] * (m + 1)
    for i in range(m):
        c[i], h[i] = map(int, input().split())
    mh = sum(h)
    dp = [0] + [float('inf')] * mh
    for i in range(m):
        for j in range(mh, h[i] - 1, -1):
            if i * x >= dp[j - h[i]] + c[i]:
                dp[j] = min(dp[j], dp[j - h[i]] + c[i])
    for i in range(mh, -1, -1):
        if dp[i] != float('inf'):
            print(i)
            break

link： https://codeforces.com/contest/1974/problem/E

"""
1.背包容量 capacity, n 件物品
2.n件物品的重量 w, 价值 v
"""


def knapsack_01(items, capacity):

    n = len(items)
    # dp[i][j] 代表 前 i 个物品 j 容量时的价值
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight, val = items[i - 1]
        for j in range(capacity + 1):
            if weight <= j:
                dp[i][j] = max(dp[i - 1][j], val + dp[i - 1][j - weight])
            else:
                dp[i][j] = dp[i - 1][j]

    max_val = dp[n][capacity]
    return max_val


capacity, n = map(int, input().split())
items = []
for i in range(n):
    weight, val = map(int, input().split())
    items.append((weight, val))

max_val = knapsack_01(items, capacity)
print(max_val)