NP Knapsack problem
One of the classic NP - complete problems is the so-called Knapsack problem. It is formulated as follows.
n items are given, each of which is characterized by weight w[i] and usefulness p[i]. It is necessary to choose a certain set of these items so that the total weight of this set does not exceed w, and the total usefulness is maximum.
Input
First line contains positive integers n (1 ≤ n ≤ 20) and w (1 ≤ w ≤ 10^9). Next n lines with two integers are given: the weight of the i-th item w[i] and its usefulness p[i] (1 ≤ w[i], p[i] ≤ 10^9).
Output
On the first line print the number of selected items and their total usefulness. On the second line print their numbers in ascending order (items are numbered starting from one in the order in which they are given at the input).
If there exists several outputs, choose the one with the smallest number of items. If after that the answer is still ambiguous, choose the set where the first item has the lowest possible number, from all such options, choose the one in which the second item has the lowest possible number, etc.