Cowburger Kitchen Worker

Interview

Time limit3sMemory limit512 MB

Summary
With M cheeseburgers and K fries available, pick the largest subset of orders, each requiring some of each item, that fits within both limits.
Level

Medium5 of 10

Topics
Dynamic programming, Greedy, Sorting, Brute force
Solved
No attempts yet

Problem

To celebrate the end of midterms, Yeongseok spent money without a plan and ended up with less than 100 won left in his bank account, so he decided to take a job in the Cowburger kitchen. Cowburger is a famous restaurant at Chung-Ang University that sells cheeseburgers and french fries.

On his first day, the moment Yeongseok stepped into the kitchen he realized something very important. He does not know how to make cheeseburgers, let alone french fries. Fortunately, the kitchen had a few cheeseburgers and orders of french fries left over that someone had already made, and Yeongseok decided to handle the current orders using them.

Every order consists of two integers: the required number of cheeseburgers and the required number of french fries. To handle an order, he must use exactly the number of cheeseburgers and french fries that the order requires. He can choose any order to handle regardless of the order in which they came in, and since a handled order disappears, the same order cannot be handled twice.

Unfortunately, not much is left in the kitchen, so some orders may not be handled. If he chooses orders to handle in the best way possible, what is the maximum number of orders he can handle?

Input

The first line gives the number of orders N(1≤N≤100)N(1 \le N \le 100), the number of cheeseburgers left in the kitchen M(1≤M≤300)M(1 \le M \le 300), and the number of french fries left in the kitchen K(1≤K≤300)K(1 \le K \le 300).

Each of the next NN lines gives two integers x,yx, y (1≤x,y≤300)(1 \le x, y \le 300) describing an order. xx is the required number of cheeseburgers and yy is the required number of french fries.

Output

Output the maximum number of orders that can be handled using the cheeseburgers and french fries left in the kitchen.

Examples3

  1. Example 1

    Input
    4 3 4
    2 5
    1 2
    3 3
    2 1
    
    Expected output
    2
    
  2. Example 2

    Input
    5 5 5
    5 5
    7 3
    2 9
    8 5
    2 9
    
    Expected output
    1
    
  3. Example 3

    Input
    3 4 4
    1 1
    1 1
    1 2
    
    Expected output
    3