Bài toán ba lô 5

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: 250 (p) Thời gian: 2.5s 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 phải nằm trong giới hạn từ \(L\) tới \(R\). 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 phải từ \(L\) tới \(R\), và tổng giá trị lớn nhất có thể.

Input

  • Dòng thứ nhất chứa ba số nguyên dương \(N, L, R\) là số món đồ trong siêu thị và giới hạn tổng khối lượng mà CJ phải lấy.
  • \(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

  • \(1 \leq L \leq R \leq 15.10^9\), \(W_i, V_i \leq 10^9\), với \(\forall i, 1 \leq i \leq N\).

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(N \leq 18\).
  • Subtask \(2\) (\(50\%\) số điểm): \(N \leq 36\).

Example

Test 1

Input 
3 1 8
3 1
4 3
8 2
Output 
2
1 2

Bình luận