Buy Cakes

Time Limit: 2 Seconds

Memory Limit: 65536 KB

Description

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 ai 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 bi dollars instead of the original ai 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<=105), K (0<=K<=N), and M (0<=M<=1014).

For next N lines, each line has two integers ai and bi (1<=bi<=ai<=109).

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.

Source

None

提交代码