Xếp bì thư

Xem PDF

Điểm: 450 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho \(n\) bì thư \(E = \{E_1,E_2,...,E_n\}\) , với \(E_i=(w_i,h_i)\) trong đó \(w_i,h_i\) lần lượt là chiều dài và chiều rộng của bì thư thứ \(i\).

Cho trước một tấm thẻ \(C\) kích thước \((W,H)\).

Nhiệm vụ của bạn là hãy chọn \(m\) bì thư từ tập \(E\) , giả sử đó là: \(E_{k_1},E_{k_2},...,E_{k_m}\) với \(k_i\in [1,n]\) và chúng phải thoả mãn các điều kiện sau:

  • \(C<E_{k_1}<...<E_{k_m}\)

  • \(m\) lớn nhất có thể.

Trong đó: \(U(u_1,u_2)<V(v_1,v_2)\) nếu \(u_1<v_1\)\(u_2<v_2\)

Input

  • Dòng thứ nhất chứ số \(n(1\le n\le 5000)\)\(2\) số \(W,H(1\le W,H\le 10^6)\).

  • \(n\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(w_i,h_i(1\le w_i,h_i\le 10^6)\).

Output

  • Dòng thứ nhất in ra số \(m\).

  • Dòng thứ hai, in ra \(m\) số \(k_1,k_2,...,k_m\) thoả mãn yêu cầu bài toán. Nếu có nhiều đáp án, in ra bất kì.

Example

Test 1

Input
13 30 17
53 74
67 68
70 52
62 70
50 87
17 24
87 53
44 29
30 48
8 54
77 73
42 88
43 22
Output
4
13 8 2 11 

Test 2

Input
14 28 37
9 8
17 39
49 36
49 30
13 42
70 13
53 79
44 62
35 66
30 67
42 6
74 89
20 3
85 48
Output
3
8 7 12 

Bình luận