from typing import (
    List,
)

class Solution:
    """
    @param m: An integer m denotes the size of a backpack
    @param a: Given n items with size A[i]
    @param v: Given n items with value V[i]
    @return: The maximum value
    """
    def back_pack_i_i(self, m: int, a: List[int], v: List[int]) -> int:
        # write your code here
        # dp[i][j] = max price (i this round take, j volume)
        n = len(a)
        dp = [[0] * (m+1) for _ in range(n+1)]

        for i in range(1, n+1):
            for j in range(1, m+1):
                dp[i][j] = dp[i-1][j]
                last_volume = j - a[i-1]
                if last_volume >= 0:
                    dp[i][j] = max(dp[i][j], dp[i-1][last_volume] + v[i-1])

        print(dp[-1])
        return max(dp[-1])