← 返回题目列表

AtCoder · awc0016_c

C. 选择纪念品

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

分数: 300 分

问题陈述

高桥来到纪念品商店购买旅行纪念品。店里有 N 糖果排列整齐,每种都有固定的价格和美味。

糖果编号为 1 to N.甜 i 的价格为 P_i 日元和美味 S_i.

高桥想要准确选择 1 甜蜜作为送给朋友青木的纪念品,满足以下所有条件:

  • 价格至少为 L 日元,最多 R 日元。
  • 好吃程度至少 T.

如果存在至少一种满足条件的糖果,他会准确选择 1 甜蜜从其中按照以下优先顺序:

  • 优先选择价格最低的(最小的) P_i).
  • 如果有多种相同价格的糖果,请选择美味程度最高的那一种(最大的) S_i).
  • 如果有多种价格相同、味道相同的糖果,则优先选择数量最少的一种。

自从甜蜜的数字 1 to N 都是不同的,这些优先级所选择的甜蜜是唯一确定的。输出所选糖果的数量。

如果没有糖果满足条件,则输出 -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
  • 第一行包含糖果的数量 N,价格下限 L,价格上限 R,以及美味的下界 T,用空格分隔。
  • 如下 N 行, i- 第行 (1 \leq i \leq N) 包含价格 P_i 和美味 S_i 的甜蜜 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