Feed Optimization for Healthy Cows

Farmer John is proud of having the healthiest cows in the world. He knows the minimum vitamin content each type of feed provides that is required for his cows. Your task is to help the farmer choose the feed types such that the cows get at least the required amount of vitamins while minimizing the number of feed types used. If there are multiple solutions with the same number of feed types, choose the one with the smallest total vitamin content.

Note that each feed type may be used at most once. The input is guaranteed to have at least one solution.

Mathematical formulation:
Find a subset S of the feed indices such that \[ \sum_{i \in S} a_i \geq V \] with |S| minimized. If there exists another subset T with \(|T| = |S|\) and \[ \sum_{i \in T} a_i < \sum_{i \in S} a_i, \] then T is preferred. Here, \(V\) is the minimum required vitamin amount and \(a_i\) is the vitamin content of the \(i^{th}\) feed.

inputFormat

The input consists of:

1. A line containing an integer V (\(1 \leq V \leq 10^6\)), the minimum required vitamin amount.
2. A line containing an integer N (\(1 \leq N \leq 20\)), the number of available feed types.
3. A line with N space separated integers, where the i^th integer represents the vitamin content \(a_i\) of the i^th feed.

It is guaranteed that there is at least one subset of feeds whose total vitamin content is at least V.

outputFormat

Output a single line starting with an integer representing the number of feed types chosen, followed by the 1-indexed indices (in ascending order) of the chosen feed types separated by spaces.

For example, if the optimal answer is to use feed type 1 and feed type 3, output:

2 1 3

sample

50
5
10 20 40 30 25

2 1 3