가방
면접 대비시간 제한1초메모리 제한1024 MB
각 데이터 셋에서 무게 합이 목표 무게와 정확히 일치하는 아이템의 최소 개수를 구합니다. 만들 수 없으면 Not possible을 출력합니다.
문제
선물 가방을 만들 때는 가능한 한 적은 물건으로 가능한 한 무거운 가방을 만들고자 합니다. 이렇게 하면 각 가방에 많은 물건을 넣지 않아도 손님들이 많이 받는다고 느끼게 됩니다. 각 가방에 얼마를 넣을지 구하는 대신, 권장 무게에 도달하기 위해 가방에 넣을 수 있는 물건의 최소 개수를 구하는 프로그램을 작성하세요.
입력
첫 줄에는 데이터 세트의 개수를 나타내는 정수 n이 하나 주어집니다. 각 데이터 세트는 세 줄로 이루어집니다. 데이터 세트의 첫 줄에는 물건의 개수 x를 나타내는 정수가 하나 주어집니다. 다음 줄에는 각 물건의 무게를 나타내는 정수 x개가 주어집니다. 마지막 줄에는 도달하려는 총 무게를 나타내는 정수가 하나 주어집니다.
출력
각 데이터 세트에 대해, 무게의 합이 목표 무게와 정확히 일치하는 물건의 최소 개수를 출력하세요. 목표 무게와 정확히 일치하도록 더할 수 없다면 Not possible을 출력하세요.