Của hồi môn

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

Công chúa con vua xứ Flatland chuẩn bị làm đám cưới với một hoàng tử xinh đẹp của nước láng giềng. Vua cha dự định sẽ dành cho con gái yêu một món quà hồi môn ấn tượng, đó là một phần dộ sưu tập đá quý của mình. Nhà vua có bộ sưu tập \(n\) viên đá quý, đánh số từ \(1\) đến \(n\). Viên thứ \(i\) có trọng lượng \(w_i\) và giá trị \(v_i\). Nhà vua muốn món quà càng có giá trị càng tốt nhưng trọng lượng cũng phải ở mức hợp lý – chỉ trong khoảng từ \(L\) đến \(R\).
Yêu cầu: Hãy chỉ ra cách chọn các viên đá quý thỏa mãn điều kiện của nhà vua.

Input

  • Dòng đầu tiên chứa \(3\) số nguyên \(n, L\) và \(R\) \((1 \le n \le 32, 0 \le L \le R \le 10^{18})\)
  • Dòng thứ \(i\) trong \(n\) dòng sau chứa \(2\) số nguyên \(w_i\) và \(v_i\) \((1 \le w_i, v_i \le 10^{15})\).

Output

  • Dòng đầu tiên đưa ra số nguyên \(k\) – số viên đá được chọn.
  • Mỗi dòng trong \(k\) dòng sau chứa số nguyên trong phạm vi từ \(1\) đến \(n\) xác định viên đá được chọn.
    Nếu không thể chọn được món quà đạt yêu cầu thì đưa ra một dòng chứa số \(0\).

Example

Test 1

Input 
3 6 8
3 10
7 3
8 2
Output 
1
2

Bình luận