Farmer John's Cow Purchase

Farmer John is looking to buy as many cows as possible without exceeding his budget of (M) monetary units. There are (N) cows available. The (i^{th}) cow costs (P_i) units if bought at the regular price. However, Farmer John has (K) discount coupons. If he uses a coupon on cow (i) its price drops to (C_i) (with (1 \le C_i \le P_i)). Note that each cow can have at most one coupon applied.

The task is to determine the maximum number of cows that Farmer John can purchase with at most (M) money.

Formally, if one chooses a set (S) of cows (with (|S|=X)), and decides to use coupons on a subset (T \subseteq S) (with (|T| \le K)), the total cost will be [ \sum_{i\in S\setminus T} P_i + \sum_{i\in T} C_i = \sum_{i\in S} P_i - \sum_{i\in T} (P_i-C_i). ] It is optimal to use coupons on those cows with the largest difference (P_i-C_i) if available.

You are given (N, M, K) and then (N) pairs ((P_i, C_i)). Your task is to compute the maximum (X) ((0\le X\le N)) for which there exists a selection of (X) cows with total cost at most (M).

inputFormat

The first line contains three integers (N) (the number of cows), (M) (the total budget), and (K) (the number of coupons). Each of the next (N) lines contains two integers (P_i) and (C_i), representing the regular price and the discounted price of the (i^{th}) cow.

outputFormat

Output a single integer which is the maximum number of cows that Farmer John can afford.

sample

2 100 1
100 1
90 89

2