**Mysterious Present(pick and leave problem with backtracking of path of pick of best answer )

Mysterious Present

Peter decided to wish happy birthday to his friend from Australia and send him a card. To make his present more mysterious, he decided to make a chain. Chain here is such a sequence of envelopes A = {a1,  a2,  ...,  an}, where the width and the height of the i-th envelope is strictly higher than the width and the height of the (i  -  1)-th envelope respectively. Chain size is the number of envelopes in the chain.

Peter wants to make the chain of the maximum size from the envelopes he has, the chain should be such, that he'll be able to put a card into it. The card fits into the chain if its width and height is lower than the width and the height of the smallest envelope in the chain respectively. It's forbidden to turn the card and the envelopes.

Peter has very many envelopes and very little time, this hard task is entrusted to you.

Input

The first line contains integers n, w, h (1  ≤ n ≤ 5000, 1 ≤ w,  h  ≤ 106) — amount of envelopes Peter has, the card width and height respectively. Then there follow n lines, each of them contains two integer numbers wi and hi — width and height of the i-th envelope (1 ≤ wi,  hi ≤ 106).

Output

In the first line print the maximum chain size. In the second line print the numbers of the envelopes (separated by space), forming the required chain, starting with the number of the smallest envelope. Remember, please, that the card should fit into the smallest envelope. If the chain of maximum size is not unique, print any of the answers.

If the card does not fit into any of the envelopes, print number 0 in the single line.

Sample test(s)

input

2 1 1
2 2
2 2

output

1
1 

input

3 3 3
5 4
12 11
9 8

output

3
1 3 2 

--------------------------------------------------------editorial---------------------------------
 dp[i]= if we pic ith element than no of elements can be picked in future , means no of elements picked after picking ith element

next[i] in the best answer calculation next index which is picked after i th index 

O(N^2) dynamic programming. DP state is index of last chosen envelope, and loop over for the next envelope.

main thing in this problem is that backtracking of best path while calculating maximum chain ,,,,,
this is a very good way to keep track of path of picked elements 
------------------------------------------------------code--------------------------------------------------------------
#include<iostream>
using namespace std;
#include<bits/stdc++.h>
int n;
int next[1000000];
int dp[1000000];
vector<pair<int,int> > v;
int solve(int cur)
 {
   
  if(dp[cur]!=-1)
   {
     return dp[cur];
     
  }
  else
  {
   int cur_w=v[cur].first;
   int cur_h=v[cur].second;
   int ret=0;
   int par=cur;
    for(int j=0;j<=n;j++)
    {
       if(v[j].first>cur_w && v[j].second>cur_h)
       {
        int val=solve(j);
         if(val>ret)
          {
           ret=val;
           par=j;
   }
 }
   }
   dp[cur]=ret+1;
   next[cur]=par;
   return dp[cur];
  }
  } 
  
  int main()
   {
   
      cin>>n;
      for(int i=0;i<=n;i++)
       {
        dp[i]=-1;
         int a,b;
          cin>>a>>b;
          v.push_back(make_pair(a,b));
  }
  
 
  int ans=solve(0);
  
   cout<<ans-1<<endl;
   int start=next[0];
   for(int i=0 ;i<ans-1;i++)
    {
     cout<<start<<" ";
     start=next[start];
}
  

   }

------------------------------------------------another editorial-----------------------------------------------------

Mysterious Present

Problem can be solved by dynamic programming approach for O(n2) by time and O(n) by memory.

1. Sort all envelopes by pairs (wi, hi) or by product wi*hi in nondecreasing order. Because of it envelope i can be put in envelope j only ifi < j. That is for any chain {a1, a2, ..., an} is true that a1 < a2 < ... < an.
2. Just delete all envelopes in which card can't be put in.
3. Add to sorted envelopes array a0 - Peter's card.
4. Introduce DP function: dp[i] maximum chain length which ends in i-th envelope.
5. dp[0] = 0, dp[i] = max(dp[j]) + 1, where i ≥ 1, 0 ≤ j < i and j can be put in i. This function can be easily got by previously computed values of it.

Problem answer is max(dp[i]), where 0 ≤ i ≤ n.
For each dp[i] one can remember index p[i] = j with which maximum reached in formula p5. If one knows s - envelope index in which maximal chain ends he can restore all answer sequence (i0 = s, ik+1 = p[ik]).