class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        dp = [-float("inf") for i in range(len(nums)+1)]
        for i in range(0,len(nums)):
            dp[i+1] = nums[i]
            for j in range(i,max(i-k,-1),-1):
                dp[i+1] = max(dp[i+1], dp[j] + nums[i])
                if j-1 >= 0 and nums[j-1]>=0:
                    break
        return max(dp)