说明

有 $M + 1$ 个单元格按顺序标记为 $0$ 到 $M$。单元格 $0$ 包含一个基地，单元格 $M$ 包含一个血量为 $H$ 的怪物。在单元格附近部署了 $N$ 名士兵。士兵 $i$ 的攻击范围是从单元格 $L_i$ 到 $R_i$（即单元格 $L_i, L_i + 1, \ldots, R_i$）。

每个回合，怪物和士兵按顺序执行以下行动（先是怪物，然后是士兵）：

• 怪物：如果怪物的血量大于等于 $1$ 且它不在单元格 $0$，则它向基地方向移动一个单元格（即移动到编号小 $1$ 的单元格）。
• 士兵：任何攻击范围包含怪物当前所在单元格的士兵会攻击怪物，使其血量减少 $1$。

如果怪物的血量在到达单元格 $0$ 之前降至 $0$ 或以下，则怪物在该单元格死亡，防御成功，游戏结束。如果怪物在血量未降至 $0$ 或以下的情况下到达单元格 $0$，则防御失败，游戏结束。

判断防御是否会成功，如果成功，找出怪物将死亡的单元格编号。

输入格式

输入包含一个单独的测试用例，格式如下：

$$\begin{aligned} &N \ M \ H \\ &L_1 \ R_1 \\ &\vdots \\ &L_N \ R_N \end{aligned}$$

第一行包含三个整数 $N$、$M$ 和 $H$，分别表示士兵数量、单元格数量和怪物的血量。$N$ 在 $1$ 到 $100,000$ 之间（含端点）。$M$ 在 $2$ 到 $10^6$ 之间（含端点）。$H$ 在 $1$ 到 $10^{11}$ 之间（含端点）。

接下来的 $N$ 行每行包含两个整数 $L_i$ 和 $R_i$，表示第 $i$ 名士兵的攻击范围区间。$L_i$ 和 $R_i$ 均在 $1$ 到 $M - 1$ 之间（含端点）。保证 $L_i$ 小于等于 $R_i$。

输出格式

输出一个整数。如果防御成功，输出怪物将死亡的单元格编号；否则输出 $-1$。

2 5 3
2 4
3 4

3

4 5 10
1 2
2 4
4 4
3 4

-1

提示

翻译由 DeepSeek V3.2 完成