该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

星空摄影

题目描述

夜空可以看作一条一维数轴。天空中分布着 $n$ 颗星星，第 $i$ 颗星星的位置为 $x_i$，亮度为 $v_i$。

你拥有一台视野宽度为 $L$ 的望远镜。如果你将望远镜的左端对准坐标 $p$，那么它能覆盖的闭区间为 $[p, p+L]$。只有位置在这个区间内的星星会被拍到。

为了拍摄一张完美的照片，你需要从视野内包含的所有星星中，挑选出恰好 $k$ 颗星星作为主角。

（注意：如果视野内包含的星星数量超过 $k$ 颗，你可以自由选择其中任意 $k$ 颗；如果不足 $k$ 颗，则无法拍摄）。

这张照片的“星空质量”定义为：你所选出的这 $k$ 颗星星中，亮度最小的那颗星的亮度值。

请问：通过选择合适的拍摄位置 $p$ 以及合适的 $k$ 颗星星，你能得到的最大“星空质量”是多少？

如果无法拍到至少 $k$ 颗星星，请输出 -1。

输入格式

第一行包含三个整数 $n, k, L$ ($1 \le k \le n \le 10^5, 1 \le L \le 10^9$)，分别代表星星总数、需要选出的星星数量、望远镜视野宽度。

接下来的 $n$ 行，每行包含两个整数 $x_i, v_i$ ($0 \le x_i \le 10^9, 1 \le v_i \le 10^9$)，分别代表星星的位置和亮度。

注意：星星的位置不一定有序，且同一位置可能有多颗星星。

输出格式

输出一个整数，代表可能达到的最大“星空质量”。若无解则输出 -1。

输入输出样例 #1

输入 #1

5 3 5
1 10
2 20
8 30
9 40
10 50

输出 #1

30

输入输出样例 #2

输入 #2

6 4 11
1 100
5 5
12 100
15 100
16 100
20 2

输出 #2

5

说明/提示

样例1解释：

选择区间 $[5, 10]$（长度 5），视野内包含星星：$(8, 30), (9, 40), (10, 50)$。

一共恰好 3 颗，全部选入。最小亮度为 30。