카우버거 알바생

면접 대비

시간 제한3초메모리 제한512 MB

요약
치즈버거 M개와 감자튀김 K개로, 각 주문이 요구하는 두 재료의 양을 모두 넘지 않도록 최대 몇 개의 주문을 처리할 수 있는지 구한다.
난이도

보통10점 중 5점

유형
동적 계획법, 그리디, 정렬, 완전 탐색
정답자
아직 제출이 없습니다

문제

중간고사가 끝난 것을 기념해 계획 없이 돈을 쓰던 영석이는 결국 통장 잔고가 100원도 남지 않게 되었고, 카우버거 주방에서 알바를 하기로 했다. 카우버거는 치즈버거와 감자튀김을 파는 중앙대학교의 유명한 음식점이다.

알바 첫날, 주방에 들어선 영석이는 매우 중요한 사실을 깨달았다. 그는 치즈버거는 물론이고 감자튀김도 만들 줄 모른다는 것이다. 다행히도 주방에는 누군가 만들어둔 치즈버거와 감자튀김이 몇 개 남아 있었고, 영석이는 지금 들어온 주문을 이것으로 처리하기로 했다.

모든 주문은 치즈버거 요구 개수와 감자튀김 요구 개수를 나타내는 2개의 정수로 이루어진다. 어떤 주문을 처리하려면 치즈버거와 감자튀김을 정확히 그 주문에서 요구하는 만큼 써야 한다. 주문이 들어온 순서와 관계없이 원하는 주문을 골라 처리할 수 있으며, 한 번 처리한 주문은 사라지므로 같은 주문을 다시 처리할 수 없다.

주방에 남아 있는 것이 많지 않기 때문에 어떤 주문은 처리하지 못할 수도 있다. 최선의 방법으로 주문을 골라 처리한다면 최대 몇 개의 주문을 처리할 수 있을까?

입력

첫째 줄에 주문의 수 N(1≤N≤100)N(1 \le N \le 100), 주방에 남은 치즈버거 개수 M(1≤M≤300)M(1 \le M \le 300), 주방에 남은 감자튀김 개수 K(1≤K≤300)K(1 \le K \le 300)가 주어진다.

둘째 줄부터 NN개의 줄에는 주문 내용을 나타내는 두 정수 x,yx, y (1≤x,y≤300)(1 \le x, y \le 300)가 주어진다. xx는 치즈버거 요구 개수, yy는 감자튀김 요구 개수를 나타낸다.

출력

주방에 남은 치즈버거와 감자튀김을 사용해 처리할 수 있는 최대 주문 개수를 출력한다.

예제3

  1. 예제 1

    입력
    4 3 4
    2 5
    1 2
    3 3
    2 1
    
    예상 출력
    2
    
  2. 예제 2

    입력
    5 5 5
    5 5
    7 3
    2 9
    8 5
    2 9
    
    예상 출력
    1
    
  3. 예제 3

    입력
    3 4 4
    1 1
    1 1
    1 2
    
    예상 출력
    3