分数: 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