RUN을 다시 위대하게

KAIST 동아리 연합은 대학 동아리 지원금을 동아리 활동 기록을 바탕으로 배정하는 학생 단체이다. 태인은 KAIST의 마라톤 동아리 RUN의 회원이며, RUN의 지원금을 늘리기 위해 KAIST 동아리 연합에 가입했다.

KAIST에는 1번부터 $N+1$번까지 번호가 붙은 $N+1$개의 동아리가 있다. RUN의 번호는 $N+1$이다. KAIST 동아리 연합은 각 동아리에 0 이상의 정수인 점수를 부여한다. 동아리의 순위는 (자신보다 점수가 높은 동아리의 수)+1로 정의한다. 같은 순위의 동아리가 여러 개 있을 수 있다. 순위가 낮을수록 동아리가 지원금을 받을 기회가 커진다.

태인은 RUN에 유리하도록 점수를 조작하려 한다. 현재 RUN을 제외한 모든 동아리의 점수는 정해져 있다. 즉, 각 $1\le i\le N$에 대해 동아리 $i$의 점수는 $a_i$이다. 태인은 다음 조건에 따라 각 동아리의 점수를 바꿀 수 있다.

• 변경 후 각 동아리의 점수는 올라가면 안 된다.
• 변경 후 각 동아리의 점수는 0 이상의 정수여야 한다.
• 태인이 동아리 $i$의 점수를 $T$만큼 낮추면, KAIST 동아리 연합의 의심 지수가 $T \times b_i$만큼 올라간다. 여기서 $b_i$는 각 동아리의 영향력과 정보 수집 능력에 따라 정해진 정수이다.
• 의심 지수의 합은 $K$보다 작아야 한다. $K$ 이상이면 내부 조사가 시작되어 태인에게 문제가 생길 수 있다.

점수를 조작한 뒤 태인은 RUN의 점수를 정해 지원금 배정 절차를 마친다.

의심을 피하려고 태인은 필요한 지원금을 모두 받을 수 있을 만큼 순위를 충분히 높게 유지하면서, RUN의 점수를 가능한 한 낮게 두려 한다. RUN의 최종 순위가 $X$ 이하이고, 의심 지수를 $K$보다 적게 올리는 조작 방법이 존재하도록 하는 RUN의 가장 낮은 초기 점수를 구하라. RUN도 동아리이므로 이 점수 역시 0 이상의 정수여야 한다.

첫 줄에 공백으로 구분된 $N$, $K$, $X$가 주어진다.

이후 $N$개의 줄 중 $i$번째 줄에는 공백으로 구분된 $a_i$와 $b_i$가 주어진다.

조건을 만족하는 RUN의 가장 낮은 초기 점수를 출력한다. RUN의 최종 순위가 $X$ 이하이고, 의심 지수를 $K$보다 적게 올리는 조작 방법이 존재해야 한다. RUN도 동아리이므로 이 점수 역시 0 이상의 정수여야 한다.

• $1\leq N\leq 10^{5}$
• $1\leq K\leq 10^{18}$
• $1\leq X\leq N+1$
• $0\leq a_{i}\leq 10^{6}$
• $1\leq b_{i}\leq 10^{6}$