Dynamic Programming solution for one pile nim game

I have solved the following problem using dynamic programming: Little Deepu and his Girlfriend 1. To paraphrase,

We have two players Little Deepu and Kate and M items in the bag B, also we have a game set S with N elements, each element of game set is an integer. The game is played as follows, each player takes turn to pick an element from the game set S and removes that number of items from the bag, the player that is unable to remove the items from the bag looses the game. Little Deepu start the game ,If both Little Deepu and Kate play the game optimally, your task is to determine who wins the game.

Input: First line contains a integer T , number of test cases. Each test case contain two lines , first line contain two integer M and N and second line contain elements of S.

Output: For each test case print name of the winner of the game .

Though correct, my solution is exceeding time limit for large inputs. Please tell me where I am going wrong.

def winner(n_i, n_t, t_k):
    output = [False]*(n_i + 1)
    for j in t_k:
        output[j    ] = True
    print(output)
    for i in range(1, n_i + 1):
        if not output[j]:
            for j in t_k:
                if j > i:
                    continue
                val = output[i - j]
                if not val:
                    output[i] = True
                    break
    return 'Little Deepu' if output[n_i] else 'Kate' 

num_test = int(input())

for i in range(num_test):
    num_items,num_take_outs = map(int, input().split())
    take_outs = list(map(int, input().split()))
    print(winner(num_items, num_take_outs, take_outs))