C - Choosing Souvenirs Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は旅行のお土産を買うために、お土産屋さんにやってきました。店には N 個のお菓子が並んでおり、それぞれに値段と美味しさが設定されています。

お菓子には 1 から N までの番号が付けられており、お菓子 i の値段は P_i 円、美味しさは S_i です。

高橋君は、友人の青木君へのお土産として、以下の条件をすべて満たすお菓子を 1 つ選びたいと思っています。

  • 値段が L 円以上 R 円以下である。
  • 美味しさが T 以上である。

条件を満たすお菓子が 1 つ以上存在する場合、その中から以下の優先順位に従ってちょうど 1 つのお菓子を選びます。

  • 値段が最も安い（ P_i が最も小さい）ものを優先する。
  • 値段が同じものが複数ある場合、美味しさが最も高い（ S_i が最も大きい）ものを優先する。
  • 値段も美味しさも同じものが複数ある場合、番号が最も小さいものを優先する。

お菓子の番号は 1 から N まで互いに異なるため、この優先順位により選ばれるお菓子は一意に定まります。選ばれたお菓子の番号を出力してください。

条件を満たすお菓子が 1 つも存在しない場合は -1 を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L \leq R \leq 10^9
  • 1 \leq T \leq 10^9
  • 1 \leq P_i \leq 10^9 （ 1 \leq i \leq N ）
  • 1 \leq S_i \leq 10^9 （ 1 \leq i \leq N ）
  • 入力はすべて整数である。

入力

N L R T
P_1 S_1
P_2 S_2
\vdots
P_N S_N
  • 1 行目には、お菓子の個数 N 、値段の下限 L 、値段の上限 R 、美味しさの下限 T が空白区切りで与えられる。
  • 続く N 行のうち i 行目（ 1 \leq i \leq N ）には、お菓子 i の値段 P_i と美味しさ S_i が空白区切りで与えられる。

出力

条件を満たすお菓子が存在する場合、上記の優先順位に従って選んだお菓子の番号を出力してください。存在しない場合は -1 を出力してください。

入力例 1

5 100 500 3
150 5
200 8
50 10
150 4
600 9

出力例 1

1

入力例 2

4 300 500 7
100 10
400 3
600 8
350 5

出力例 2

-1

入力例 3

10 200 800 5
500 3
1000 10
250 9
300 6
150 8
800 5
250 9
400 7
900 12
600 4

出力例 3

3

Score : 300 pts

Problem Statement

Takahashi has come to a souvenir shop to buy souvenirs from his trip. The shop has N sweets lined up, each with a set price and deliciousness.

The sweets are numbered from 1 to N. Sweet i has a price of P_i yen and a deliciousness of S_i.

Takahashi wants to choose exactly 1 sweet as a souvenir for his friend Aoki, satisfying all of the following conditions:

  • The price is at least L yen and at most R yen.
  • The deliciousness is at least T.

If there exists at least one sweet satisfying the conditions, he will choose exactly 1 sweet from among them according to the following priorities:

  • Prefer the one with the lowest price (smallest P_i).
  • If there are multiple sweets with the same price, prefer the one with the highest deliciousness (largest S_i).
  • If there are multiple sweets with the same price and the same deliciousness, prefer the one with the smallest number.

Since the sweet numbers from 1 to N are all distinct, the sweet chosen by these priorities is uniquely determined. Output the number of the chosen sweet.

If no sweet satisfies the conditions, output -1.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq L \leq R \leq 10^9
  • 1 \leq T \leq 10^9
  • 1 \leq P_i \leq 10^9 （ 1 \leq i \leq N ）
  • 1 \leq S_i \leq 10^9 （ 1 \leq i \leq N ）
  • All inputs are integers.

Input

N L R T
P_1 S_1
P_2 S_2
\vdots
P_N S_N
  • The first line contains the number of sweets N, the lower bound of price L, the upper bound of price R, and the lower bound of deliciousness T, separated by spaces.
  • In the following N lines, the i-th line (1 \leq i \leq N) contains the price P_i and deliciousness S_i of sweet i, separated by spaces.

Output

If there exists a sweet satisfying the conditions, output the number of the sweet chosen according to the above priorities. If no such sweet exists, output -1.

Sample Input 1

5 100 500 3
150 5
200 8
50 10
150 4
600 9

Sample Output 1

1

Sample Input 2

4 300 500 7
100 10
400 3
600 8
350 5

Sample Output 2

-1

Sample Input 3

10 200 800 5
500 3
1000 10
250 9
300 6
150 8
800 5
250 9
400 7
900 12
600 4

Sample Output 3

3