'''
题目描述可知,只要帖子在D时间段内有k个点赞就输出答案
因为题目的帖子编号很小,我们可以用桶装每一个对应编号的帖子的点赞记录
桶里就放点赞的时间即可
(py的list和C++的vector一样可以像一个链表一样储存这些数据 所以不会爆内存)
处理完后的帖子记录 我们从前往后搜索id 如果有id的点赞总数不少于k则进一步计算时间段
是否满足目标
'''
import sys
N, D, K = map(int, input().split())
data = []
maxn = 100010
tiezhi = [[] for i in range(maxn)]
# 读入帖子数组 并且按照时间顺序排列 时间一样,以id顺序排列
for i in range(N):
data.append(list(map(int, sys.stdin.readline().strip().split())))
# data.append(list(map(int, input().split())))
data.sort()
# 将排序好的数组导入桶中
for i in data:
tiezhi[i[1]].append(i[0])
for i in range(maxn):
# 若该id的点赞数大于等于要求 则用滑动窗口判断正确性
if len(tiezhi[i]) >= K:
j = K - 1
# 取前k个元素
# 因为时间顺序已经事先排序 所以q中的序列一定是有序的
# 只要求解第一个与最后一个的差是否满足要求即可
q = tiezhi[i][:K]
while j < len(tiezhi[i]):
if q[-1] - q[0] < D:
print(i)
break
else:
# 不满足则将双指针区间整体右移一个单位
j += 1
if j == len(tiezhi[i]): break
q.pop(0)
q.append(tiezhi[i][j])
$O(n)=n*log(n)$