import sys sys.setrecursionlimit(1 << 25) def main(): T = int(sys.stdin.readline()) N = int(sys.stdin.readline()) t = [int(sys.stdin.readline()) for _ in range(N)] t.sort(reverse=True) # Sort in descending order for efficiency # Precompute the sum of all possible subsets precomputed_sums = [0] * (1 << N) for mask in range(1 << N): s = 0 for i in range(N): if mask & (1 << i): s += t[i] precomputed_sums[mask] = s def can_assign(groups_left, mask, memo): if mask == 0: return True if groups_left == 0: return False key = (groups_left, mask) if key in memo: return memo[key] # Find the first unassigned problem first = 0 for i in range(N): if (mask >> i) & 1: first = i break s = mask ^ (1 << first) subset = s success = False while True: current_subset = subset | (1 << first) total = precomputed_sums[current_subset] if total <= T: new_mask = mask ^ current_subset if can_assign(groups_left - 1, new_mask, memo): success = True break if subset == 0: break subset = (subset - 1) & s memo[key] = success return success for k in range(1, N + 1): memo = {} full_mask = (1 << N) - 1 if can_assign(k, full_mask, memo): print(k) return print(N) # This line is theoretically unreachable if __name__ == "__main__": main()