A+를 향하여

오늘은 컴퓨터 알고리즘 과목의 기말고사가 있는 날이다. 이번 시험 공부를 위해 전날 밤을 꼬박 새우고 시험장에 도착한 달구는, 시험 시작 시간이 되어 시험지를 받아들었다. 시험지에는 총 $N$개의 문제가 있었으며, 시험 종료 시각은 앞으로 $T$분 후였다. 시험지의 모든 문제를 빠르게 훑어본 결과 $i$번 문제를 풀기 위해 걸리는 예상 시간 $t_i$와 풀었을 때 얻을 수 있는 점수 $w_i$를 알아냈다. 또한, 이번 시험에서 최소 $W$점 이상은 받아야 이번 학기에 A+를 받을 수 있다는 사실까지 깨달았다.

그러나 시험 문제를 풀려던 찰나, 전날 밤을 새운 달구에게 갑작스럽게 졸음이 쏟아졌다! 잠깐 자고 일어나면 더 효율적으로 문제를 풀 수 있으리라 생각한 달구는, 잠깐 자고 일어나서 문제를 풀고자 한다.

달구가 문제를 풀기 전에 정수 $x$분 자고 일어나면, 각 문제를 해결하는 데 걸리는 시간이 정확히 $x$분씩 줄어들어 $i$번 문제를 푸는 데 걸리는 시간이 $\max(0, t_i-x)$가 된다고 한다. 단, 자는 시간도 시험 시간에 포함되므로, $x$분을 자고 나면 문제를 풀 수 있는 시간은 $(T-x)$분이 된다. 달구는 시험 시간인 $T$분 이하의 시간 동안만 잘 수 있으며, 만약 자고 일어난 뒤 남은 시간이 $0$분이라도 소요 시간이 $0$분인 문제는 전부 풀 수 있다.

이번 학기 A+를 목표로 하는 달구는 반드시 이번 시험에서 $W$점 이상을 받고자 한다. 또한, 시험장에서 너무 오래 자기에 눈치가 보인 달구는 $W$점 이상을 받을 수 있다면 최소 시간만 자고 일어나서 시험 문제를 풀고자 한다. 달구가 이번 시험에서 $W$점 이상을 받기 위해 잠깐 자야 하는 최소 시간을 구해주자.

첫째 줄에 문제의 개수 $N$, 시험 종료까지 남은 시간 $T$, 목표 점수 $W$가 공백으로 구분되어 정수로 주어진다. ($1\leq N, T\leq 2\,500$; $1\leq W\leq 10^{9}$)

둘째 줄부터 $N$개의 줄에 걸쳐 각 문제의 예상 풀이 시간 $t_i$와 점수 $w_i$가 공백으로 구분되어 정수로 주어진다. ($1\leq t_i, w_i\leq 2\,500$)

$W$점 이상을 받기 위해 자야 하는 최소 시간을 출력한다. 만약 $W$점 이상을 받을 수 없다면, -1을 출력한다.