← 返回题目列表

Codeforces · 4/D

D. 神秘礼物

中文机器翻译题面 查看原题

彼得决定祝他来自澳大利亚的朋友生日快乐,并给他寄一张卡片。为了让他的礼物更加神秘,他决定制作一条链子。这里的 Chain 是这样的信封序列 A = {a1, a2, ..., an},其中第 i 个信封的宽度和高度分别严格高于第 (i - 1) 个信封的宽度和高度。链大小是链中信封的数量。

彼得想用他拥有的信封制作最大尺寸的链条,链条应该是这样的,他能够将卡片放入其中。如果卡片的宽度和高度分别低于链中最小信封的宽度和高度,则卡片适合链中。禁止翻转卡片和信封。

Peter的信封非常多,时间却很少,这个艰巨的任务就交给你了。

输入

第一行包含整数 n、w、h (1 ≤ n ≤ 5000, 1 ≤ w, h ≤ 106) — Peter 拥有的信封数量、卡片的宽度和高度。接下来是n行,每行包含两个整数wi和hi——第i个信封的宽度和高度(1≤wi,hi≤106)。

输出

在第一行打印最大链条尺寸。在第二行中打印信封的编号(用空格分隔),形成所需的链,从最小的信封的编号开始。请记住,卡片应能装入最小的信封中。如果最大尺寸的链不是唯一的,则打印任何答案。

如果卡片无法装入任何信封,请在单行中打印数字 0。

示例

输入 #1

2 1 1
2 2
2 2

输出 #1

1
1

输入 #2

3 3 3
5 4
12 11
9 8

输出 #2

3
1 3 2