EIU Programming Practices and Exams

You are given N items, each with a weight and a value. You have a knapsack with weight capacity W. Your goal is to select a subset of items such that:

1. The total weight does not exceed W
2. The total value is maximized

Output the indices of the selected items (in any order).

Input Format

The first line contains two integers N and W:

• N (1 ≤ N ≤ 2000): number of items
• W (1 ≤ W ≤ 50000): maximum weight capacity

The next N lines contain two integers each:

• wi vi: weight and value of the i-th item (1 ≤ wi ≤ W, 1 ≤ vi ≤ 10^4)

Output Format

The output consists of two lines:

• First line: The maximum total value that can be achieved
• Second line: The indices of selected items in any order, separated by spaces

Items are numbered from 1 to N.

If no items can be selected, output 0 on the first line and an empty second line.

Example

Input

4 5
2 1
1 2
3 3
2 2

Output

5
3 2 

Explanation

• Item 1: weight=2, value=1
• Item 2: weight=1, value=2
• Item 3: weight=3, value=3
• Item 4: weight=2, value=2

Selecting items 2 and 3: total weight = 1+3 = 4 ≤ 5, total value = 2+3 = 5 This gives the maximum possible value of 5. The output shows the maximum value (5) on the first line and the selected items (3, 2) on the second line.

Notes

• Multiple optimal solutions may exist. Any valid optimal solution will be accepted.
• The order of output indices doesn't matter.
• Make sure the total weight doesn't exceed the capacity W.

Constraints

• Time limit: 1 second
• Memory limit: 256 MB
• 1 ≤ N ≤ 2000
• 1 ≤ W ≤ 50000
• 1 ≤ wi ≤ 10⁴
• 1 ≤ vi ≤ 10⁴