Bài toán ba lô 3

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
hhoangcpascal
Dạng bài
Điểm: 1900 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong siêu thị có \(N\) đồ vật, đồ vật thứ \(i\) có khối lượng là \(W_i\), và có giá trị là \(V_i\). Một ngày, CJ vào siêu thị để mua đồ. Vì trước kia mua nhiều ở đây, nên CJ được một tấm thẻ đặc biệt của siêu thị. Khi có tấm thẻ này thì CJ được quyền lấy một số món đồ sao cho tổng khối lượng không quá \(M\). Vì CJ không giỏi tính toán, nên các bạn hãy giúp CJ lấy một số món đồ sao cho tổng khối lượng không quá \(M\), và tổng giá trị lớn nhất có thể.

Input

  • Dòng thứ nhất chứa hai số nguyên dương \(N, M\) là số món đồ trong siêu thị và tổng khối lượng tối đa trong tấm thẻ.
  • \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(W_i\), \(V_i\) lần lượt là khối lượng và giá trị của đồ vật thứ \(i\).

Output

  • Dòng thứ nhất in ra số món đồ mà CJ lấy để tổng giá trị đạt lớn nhất.
  • Dòng thứ hai in ra chỉ số các món đồ mà CJ lấy theo thứ tự tăng dần.

Constants

  • \(N \leq 18, M \leq 5.10^9\)
  • \(W_i, V_i \leq 10^9\), với \(\forall i, 1 \leq i \leq N\).

Example

Test 1

Input 
5 20
7 1
5 8
1 1
7 8
9 7
Output 
4
1 2 3 4

Bình luận