class Solution:
    def lengthOfLongestSubsequence(self, nums: List[int], target: int) -> int:

        # DP with a storage of dp[nums_length, target], where dp[i,j] is the sequence that goes from nums[i:] reaching target
        import numpy as np
        
        N = len(nums)
        dp = np.zeros((N, target+1), dtype = int)
        
        if nums[0] <= target:
            dp[0, nums[0]] = 1
        
        for i in range(1, N):
            temp1 = np.zeros((target+1), dtype = int)
            for j in range(target+1-nums[i]):
                if j + nums[i] <= target:
                    if dp[i-1, j] != 0:
                        temp1[j+nums[i]] = dp[i-1, j]+1
            for j in range(target+1):
                dp[i,j] = max(dp[i-1, j] , temp1[j])
            if nums[i] <= target:
                dp[i,nums[i]] = max(dp[i,nums[i]], 1)
                
        if dp[N-1,target] == 0:
            return -1
        return dp[N-1,target]

[37,44,20,88,58,61,52,56,66,46,77,28,82,2,3,31,48,62,33,9,73,81,77,84,43,27,74,93,96,28,78,59,34,50,7,8,79,44,36,7,74,87,72,44,67,65,10,45,66,31,88,7,22,55,23,99,62,100,90,66,33,39,24,28,79,8,50,30,17,42,57,21,63,3,59,80,47,79,39,28,12,88,19,66,18,86,1,73,76,79,53,46,31,75,31,43,31,39,47,44,100,8,68,57,4,20,50,20,58,2,53,52,83,93,62,26,73,99,4,94,17,65,9,18,51,68,38,11,9,77,58,51,1,75,39,74,81,91,58,8,77,4,86,39,64,87,89,65,79,12,53,84,54,15,10,35,7,40,56,76,99,9,22,10,2,26,93,74,68,13,11,7,91,97,28,96,24,34,92,79,40,46,61,98,31,33,43,51,29,77,20,74,90,87,22,39,80,43,49,12,16,61,90,50,58,21,14,57,73,64,15,8,27,88,87,18,12,92,62,50,26,3,70,1,22,79,50,73,52,23,45,97,51,83,94,43,85,29,75,25,92,48,3,6,91,84,32,6,31,4,53,100,74,2,12,18,50,93,30,38,12,29,7,33,79,38,48,96,57,43,77,100,50,55,42,41,63,80,16,33,72,25,85,43,94,39,27,12,79,10,8,79,22,28,62,79,96,3,62,26,82,96,48,43,99,6,21,41,5,77,73,90,18,91,73,5,36,88,96,51,8,88,86,27,27,9,22,93,19,6,6,21,46,23,36,35,19,7,96,85,52,3,68,89,41,79,44,24,29,84,66,53,46,90,74,91,70,72,10,64,89,44,7,2,54,61,40,58,36,44,34,72,37,78,38,22,95,67,89,43,52,59,34,41,41,74,1,64,59,33,82,77,91,45,1,64,85,76,42,29,38,88,58,74,89,90,70,79,72,40,89,40,24,78,12,19,43,70,84,83,39,67,48,81,89,55,34,34,41,5,23,85,60,57,61,10,24,6,57,61,17,69,71,20,34,9,51,61,96,47,73,53,5,92,4,26,23,43,80,82,52,12,63,42,59,44,58,61,62,92,98,21,58,53,20,10,73,30,97,78,99,89,46,96,86,91,13,25,13,3,58,87,15,41,99,63,48,80,80,47,29,31,75,49,14,97,20,49,95,65,33,90,49,60,49,81,92,50,21,98,70,45,64,48,80,78,11,98,36,81,18,15,31,3,100,83,92,37,11,90,30,29,22,97,9,92,93,2,69,2,59,41,11,99,100,1,13,46,77,60,44,51,65,95,98,36,51,84,22,99,49,26,82,45,48,53,23,38,36,65,75,53,85,22,9,10,20,7,77,33,38,100,28,91,42,86,96,94,46,68,85,92,67,12,93,61,18,61,100,44,18,18,66,69,79,70,64,24,98,49,33,69,91,28,6,6,46,11,91,90,81,72,4,22,85,60,45,34,70,81,46,41,34,84,63,12,15,43,36,21,82,71,7,60,52,63,20,57,92,100,11,90,43,38,6,1,77,22,70,70,42,69,41,29,12,92,17,88,62,39,9,70,26,53,38,31,7,5,7,14,77,95,66,88,55,33,40,30,3,10,49,61,48,51,35,49,92,80,53,15,34,18,100,5,91,32,72,90,97,89,42,31,29,55,42,82,8,51,78,92,67,85,87,88,76,63,24,31,47,63,67,90,90,44,7,40,76,93,5,90,16,85,52,14,53,76,49,76,79,44,2,72,16,58,51,99,62,12,23,54,19,94,61,56,85,30,29,78,41,20,67,68,34,100,22,53,80,24,67,29,27,75,16,88,85,22,74,5,69,72,99,12,100,35,92,21,86,42,79,37,12,74,97,57,44,17,65,16,96,10,26,60,97,58,70,91,71,39,83,94,41,47,78,39,94,38,92,36,68,39,93,74,18,78,63,88,85,76,21,41,16,71,27,56,47,15,47,77,9,44,66,60,56,25,62,4,61,87,72,98,8,50,72,93,88,39,53,38,67,68,64,2,79,15,25,75,71,44,45,4,29,71,50,94,93,64,60,20,73,45,16,56,36,62,85,33,73,66,52,60,59,3,70,74,59,8,30,47,14,34,78,20,78,75,12,52,24,67,79,92,61,95,30,17,84,58,65,48,16,26,51,17,65,64,76,94,44,24,33,93,2,82,79,62,61,84,99,62,98,13,43,59,9,23,55,5,83,19,25,98,19,42,35,9,83,95,87,38,36,71,76,93,79,53,43,67,2,80,16,52,32,67,78,22,87,30,9,62,78,85]
1000