from typing import (
    List,
)

class Solution:
    """
    @param n: the money of you
    @param prices: the price of rice[i]
    @param weight: the weight of rice[i]
    @param amounts: the amount of rice[i]
    @return: the maximum weight
    """
    def back_pack_v_i_i(self, n: int, prices: List[int], weight: List[int], amounts: List[int]) -> int:
        # write your code here
        m = len(prices)
        dp = [[0]*(n+1) for _ in range(2)] # rotated array
        num_of_selected_items = 0

        for i in range(m): # take one kind of price
            for get_j_amount in range(1, amounts[i]+1): # get j amount 
                num_of_selected_items += 1
                for current_price in range(prices[i], n+1): 
                    dp[num_of_selected_items%2][current_price] = dp[(num_of_selected_items-1)%2][current_price]
                    last_price = current_price - prices[i]
                    if last_price >= 0:
                        dp[num_of_selected_items%2][current_price] = max(dp[num_of_selected_items%2][current_price], dp[(num_of_selected_items-1)%2][last_price] + weight[i]) 
                # print(i, get_j_amount, dp)

        return dp[num_of_selected_items%2][-1]