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

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

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<=10^{5}), `K` (0<=K<=N), and `M`
(0<=M<=10^{14}).

For next `N` lines, each line has two integers
`a _{i}` and

提交代码