농부 존은 새 소들이 필요하다! 그래서 농부 존은 소 시장에 가서 새 소들을 사려고 한다.

농부 존은 돈이 많이 없기 때문에 소들을 최대한 효율적으로 사야 한다. 그래서 농부 존은 M원과 K개의 소 쿠폰을 가지고 소 시장에 나온 N마리의 소들을 최대한 많이 사려고 한다.

소 쿠폰은 소 한 마리당 한 번만 쓸 수 있고, 쓰고 나면 사라진다. i번째 소는 P_i원이고, 쿠폰을 썼을 때는 C_i원이 될 때, 농부 존이 최대로 살 수 있는 소의 마릿수를 출력하라.

입력 형식

첫 번째 줄에 소 시장에 나온 소들의 마릿수 N(1 ≤ N ≤ 50,000), 농부 존이 가지고 있는 쿠폰의 개수 K(1 ≤ K ≤ N), 농부 존이 가지고 있는 돈 M(1 ≤ M ≤ 10¹⁴)이 주어진다.

다음 줄부터 P_i (1 ≤ P_i ≤ 10⁹), C_i (1 ≤ C_i ≤ P_i)가 주어진다.

출력 형식

농부 존이 최대로 살 수 있는 소 마릿수를 출력하라.

예제 입력

4 1 7
3 2
2 2
8 1
4 3

예제 출력

3

힌트

농부 존은 1개의 쿠폰과 7원을 가지고 소 시장에 갔다.

3번째 소에 쿠폰 하나를 쓰고 1,2,3번 소를 산다. (1 + 2 + 3 = 6원)