問題
규철이는 최근 World Of Warcraft에 심취해있다. 퀘스트를 위해서는 여러 개의 아이템을 캐릭터의 가방에 넣어서 가지고 다녀야 한다. 규철이는 N개의 아이템을 가지고 있고, 게임상에서 속임수를 이용하여 각 아이템을 무한대로 사용할 수 있다. 각 아이템에는 무게가 있으며, 가지고 있는 아이템의 무게의 합이 가방에 들어갈 수 있는 무게 이하 만큼 아이템을 넣어 다닐 수 있다.
규철이가 퀘스트를 위해 아이템을 고르던 도중에, 가방에 넣은 아이템의 무게들의 합을 만들 수 없는 경우 중 최대 무게가 얼마일까가 궁금해졌다. 하지만 이를 바로 아는 건 쉽지가 않았다. 규철이를 도와 이 문제를 풀어보자.
入力
입력의 첫 번째 줄에는 테스트 케이스의 개수 T(T≤10)가 입력된다. 각 테스트 케이스의 첫줄에 규철이가 사용할 수 있는 아이템의 종류 N(N≤500)이 주어진다. 그리고 그 다음 줄에 아이템들의 무게가 공백을 두고 N개 주어지며, 아이템 하나의 최대 무게는 5,000이다.
出力
테스트 케이스별로 한 줄씩 만들 수 없는 경우 중 가장 큰 무게를 출력한다. 채울 수 없는 가방이 무한하다면 "INF"를 출력한다.
例題
2
3
4 9 13
2
2 4
23
INF
ヒント
ログインしないとコードを書けません。