1
import sys
2
input = sys.stdin.read
3

4
def main():
5
    data = input().strip().split()
6
    n = int(data[0])
7
    v = int(data[1])
8

9
    dp = [0] * (v + 1)
10

11
    index = 2
12
    for _ in range(n):
13
        w = int(data[index])
14
        val = int(data[index + 1])
15
        index += 2
16

17
        if w > v:
18
            continue
19

20
        # 完全背包，容量正序遍历
21
        for j in range(w, v + 1):
22
            dp[j] = max(dp[j], dp[j - w] + val)
23

24
    print(dp[v])
25

26
main()

1
class Solution:
2
    def change(self, amount: int, coins: List[int]) -> int:
3
        n = len(coins)
4
        dp = [[0] * (amount + 1) for _ in range(n + 1)]
5
        # 金额为0时，只有一种组合方式——什么都不选
6
        for i in range(n + 1):
7
            dp[i][0] = 1
8

9
        for i in range(1, n + 1):
10
            for j in range(1, amount + 1):
11
                if j - coins[i - 1] >= 0:
12
                    # 选择不使用当前硬币 + 选择使用当前硬币
13
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]
14
                else:
15
                    dp[i][j] = dp[i - 1][j]
16
        return dp[n][amount]

1
class Solution:
2
    def combinationSum4(self, nums: List[int], target: int) -> int:
3
        dp = [0] * (target + 1)
4
        dp[0] = 1  # 目标为0时，组合数为1（空组合）
5

6
        for t in range(1, target + 1):
7
            for num in nums:
8
                if t - num >= 0:
9
                    dp[t] += dp[t - num]
10

11
        return dp[target]

1
import sys
2
input = sys.stdin.read
3

4
def climb_stairs(n, m):
5
    dp = [0] * (n + 1)
6
    dp[0] = 1
7
    for i in range(1, n + 1):
8
        for k in range(1, m + 1):
9
            if i - k >= 0:
10
                dp[i] += dp[i - k]
11
    return dp[n]
12

13
def main():
14
    data = input().strip().split()
15
    n = int(data[0])
16
    m = int(data[1])
17
    print(climb_stairs(n, m))
18

19
main()