작업장

작업장에 똑같은 기계 두 대가 있고, 이 기계들은 여러 부품을 가공한다. 부품의 개수는 $n$개이며, 모두 $T$ 시간 단위 이내에 가공을 마쳐야 한다. $i$번째 부품의 가공 시간은 $t_i$이고, $i = 1, \dots, n$이며, 두 기계에서 모두 같다.

프로그램 workshop을 작성하여, 주어진 시간 $T$ 안에 모든 부품의 가공을 마칠 수 있는 일정이 존재하는지 판별하시오. 부품을 기계에 올리거나 다음 부품으로 바꾸는 데 걸리는 시간은 없으며, 이는 즉시 이루어진다.

첫째 줄에는 프로그램이 일정을 만들 수 있는지 검사해야 하는 부품 묶음의 개수가 주어진다. 각 묶음의 데이터는 두 줄에 걸쳐 주어진다. 그중 첫째 줄에는 $T$와 $n$이 공백으로 구분되어 주어진다. 둘째 줄에는 $t_1, t_2, \dots, t_n$이 공백으로 구분되어 주어진다.

프로그램은 입력에 주어진 묶음의 개수만큼 줄을 출력해야 한다. 각 줄에는 해당 묶음에 대해 원하는 일정을 만들 수 있으면 1, 만들 수 없으면 0을 출력한다.

• 입력의 모든 수는 양의 정수이다. 부품 묶음의 개수는 10을 넘지 않는다.
• $0 < T < 200\,001$
• $0 < n < 1\,001$
• $0 < t_i < 101$, $i = 1, 2, \dots, n$