UNBOUNDED KNAPSACK – Cái túi (mỗi gói được chọn nhiều lần)

Trong siêu thị có n gói hàng (n ≤ 100). Gói hàng thứ i có:

• Trọng lượng W[i] (1 ≤ W[i] ≤ 100)
• Giá trị V[i] (1 ≤ V[i] ≤ 100)

Một tên trộm mang theo cái túi có thể mang tối đa trọng lượng M (M ≤ 100).

Khác với bài cái túi 0/1: mỗi gói hàng có thể được chọn nhiều lần (chọn 0, 1, 2, ... lần).

Hãy xác định cách chọn các gói hàng sao cho:

• Tổng trọng lượng không vượt quá M
• Tổng giá trị là lớn nhất

Input

• Dòng 1: hai số nguyên n và M
• n dòng tiếp theo: mỗi dòng ghi W[i] và V[i]

Output

• Dòng 1: giá trị lớn nhất có thể đạt được
• Dòng 2: chỉ số các gói hàng đã chọn, mỗi chỉ số có thể xuất hiện nhiều lần (nếu lấy nhiều gói cùng loại).
  Nếu không lấy gói nào, dòng 2 để trống.

Ví dụ

Input

3 10
6 30
3 14
4 16

Output (một đáp án hợp lệ)

46
1 3

Input

2 10
3 5
4 6

Output (một đáp án hợp lệ)

16
1 1 2

(Chọn gói 1 và gói 3: tổng trọng lượng 10, tổng giá trị 46. Có thể tồn tại nhiều đáp án tối ưu khác.)