Background

土拨鼠文景在学习了一系列知识后, 非常兴奋, 他打算在接下来$n$天里做题巩固.

Description

老师$kunkka$在这$n$天里给出$n$道题目, 第$i$天给出第$i$题, 每道题目有一个难度值$d_i$和解决问题后的欢乐值$h_i$.

同时文景有一个能力值, 他只能做对难度值小于等于能力值的题目.

另外文景在做完一道题后需要休息$k$天, 才能继续做题, 即当文景第$x$天做题时, 在接下来的$x+1, x+2, ... x+k$天内都需要休息.

现在想问要使得文景至少获得$H$的欢乐值, 文景至少需要的能力值是多少?

如果无法满足条件, 则输出-1

Format

Input

第一行给出三个正整数$n, k, H$

接下来$n$行, 每行两个正整数$d_i, h_i$, 表示第$i$天的题目的难度值和欢乐值

Output

输出一个正整数, 表示文景最小的能力值, 才可以满足至少获得$H$的欢乐值

Samples

4 1 5
2 3
2 3
5 3
3 4

3

样例解释

文景参加$1, 4$场比赛, 可以获得$7$的欢乐值, 此时最小能力值为$3$

Limitation

$1 <= n <= 10^5, 1<=k<=100, 1<=d_i, h_i, H<=10^9$