func knapsack(weights []int, values []int, maxWeight int) int {
    var dfs func(capacity, pos int) int
    dfs = func(capacity, pos int) int {
        if capacity == 0 { return 0 }
        if pos == len(weights) { return 0 }
		res := dfs(capacity, pos+1) // Exclude the weight
        if capacity >= weights[pos] {  // Include the weight if capacity allows
		    res = Max(res, values[pos]+dfs(capacity-weights[pos], pos+1))
	    }
        return res
    }
    return dfs(maxWeight, 0)
}

func Max(a, b int) int { if a > b { return a }; return b }

func knapsack(weights []int, values []int, maxWeight int) int {
    memo := make([][]*int, len(weights)); for i := range memo { memo[i] = make([]*int, maxWeight+1) }

    var dfs func(capacity, pos int) int
    dfs = func(capacity, pos int) int {
        if capacity == 0 { return 0 }
        if pos == len(weights) { return 0 }
        if memo[pos][capacity] != nil { return *memo[pos][capacity] }
		res := dfs(capacity, pos+1) // Exclude the weight
        if capacity >= weights[pos] { // Include the weight if capacity allows
            res = Max(res, values[pos]+dfs(capacity-weights[pos], pos+1))
        }
        memo[pos][capacity] = &res; return res
    }
    return dfs(maxWeight, 0)
}

func Max(a, b int) int { if a > b { return a }; return b }

func knapsack(weights []int, values []int, maxWeight int) int {
    dp := make([][]int, len(weights)+1); for r := range dp { dp[r] = make([]int, maxWeight+1) }
    
    for w := 1; w <= len(weights); w++ {
        for c := 1; c <= maxWeight; c++ {
            if c >= weights[w-1] {
                dp[w][c] = Max(dp[w-1][c], values[w-1]+dp[w-1][c-weights[w-1]])
            } else {
                dp[w][c] = dp[w-1][c]
            }
        }
    }
    return dp[len(weights)][maxWeight]
}

func Max(a, b int) int { if a > b { return a }; return b }