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.

None