The daughter of the King of Flatland is about to marry Prince Charming.
The prince wants to give the princess treasures, but he is not sure which diamonds to choose from his collection.
There are n diamonds in the prince's collection, each characterized by weight w
i and value v
i.
The prince wants to give the most expensive diamonds, but the king is smart and will not accept diamonds with a total weight of more than R. On the other hand, the prince will consider himself greedy for the rest of his life if he gives diamonds with a total weight of less than L.
Help the prince choose a set of diamonds with the highest total value so that the total weight is in the segment [L, R].
Input:
The first line contains the number n (1 <= n <= 32), L and R (0 <= L <= R <= 10
18).
The next n lines describe the diamonds and contain two numbers each - the weight and value of the corresponding diamond (1 <= wi, vi <= 10
15).
Output:
The first line of the output should contain k - the number of diamonds to give to the princess.
The second line should contain the numbers of the diamonds to be given.
Diamonds are numbered from 1 to n in the order they appear in the input.
If it is impossible to compose a present for the princess, then print 0 in the first line of the output.
Examples:
| Input |
Output |
3 6 8
3 10
7 3
8 2 |
1
2 |