TopCoder

dbGIs
\(・ω・\)SAN値!(/・ω・)/ピンチ!

User's AC Ratio

100.0% (5/5)

Submission's AC Ratio

100.0% (5/5)

Tags

Description

現在地上有 N 條鐵棒,第 i 條的長度為 li。你的目標是要利用這些鐵棒,焊出一條長度為 L 的長鐵棒,請問有辦法嗎?兩條鐵棒如果長度分別為 ab,那它們兩個焊起來之後就會變成一條長度為 a+b 的鐵棒,而且這些鐵棒可以任意焊接。

此外,你必須要回答出 T 種這個問題。

Input Format

輸入的第一行有一個數字 T(1T50),代表有幾個問題。對於每一個問題,都會有兩行的輸入:第一行有兩個數字 L(1L1000)N(1N30),代表目標長度的鐵棒與現在有幾根鐵棒。下一行有 N 個數字 li(1li1000),代表目前有的鐵棒的長度。保證所有輸出的數字都是正整數。

Output Format

對於每一筆測資,請輸出一行:倘若能夠達到目標的話,請輸出 TAK;否則,請輸出 NO

Sample Input 1

4
8 12
61 47 2 75 66 49 33 2 6 18 61 17
7 8
1 1 1 1 1 1 1 2
8 7
1 1 1 1 1 1 1
19 6
18 36 2 8 9 12

Sample Output 1

TAK
TAK
NO
TAK

Sample Input 2

4
10 4
2 3 4 5
9 4
2 3 4 5
63 6
1 2 4 8 16 32
64 6
1 2 4 8 16 32

Sample Output 2

TAK
TAK
TAK
NO

Hints

Problem Source

UVa 12455 - Bars

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~11 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2