Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3916
Buy Cakes

Time Limit: 2 Seconds      Memory Limit: 65546 KB

Andy is always a hungry man. He never stopped eating something sweet, expecially cakes.

Yesterday his mother gave him some pocket money, and now, he has M dollars all together.

The cake shop provides N pieces of cakes, and each of them costs a[i] dollars respectively.

Fortunately, Andy has K discount coupons for that cake shop. When we use a coupon, we can buy a cake at a lower prize of b[i] dollars instead of the original a[i] dollars.

So, Andy wants you to help him find out how many cakes he can buy at most.

Input

There are multiple cases.

The first line contains the number of cases for this problem T (1<=T<=10).

For each case, the first line contains three integers N (1<=N<=100,000), K (0<=K<=N), and M (0<=M<=10^14).

For next N lines, each line has two integers a[i] and b[i] (1<=b[i]<=a[i]<=10^9).

Output

For each case, output the number of cakes he can get at most.

Sample Input

2
4 1 7 
3 2 
2 2  
8 1  
4 3 
2 0 3
5 4
6 3

Sample Output

3
0

Hint

One of the solution for first case of sample input is to choose candy 1, 2, 3, and use the coupon on candy 3.


Author: WANG, Qin
Source: ZOJ Monthly, February 2016
Submit    Status