Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 3916

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.

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

```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