stevenfan@stevenfan usaco $  cat coupons.cpp
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>

using namespace std;
typedef long long ll;

struct item {
  int price, id;
  int not_discounted;
  bool discounted;
};
bool operator< (const item& a, const item& b) {
  return a.price == b.price ? a.not_discounted > b.not_discounted : a.price < b.price;
}

int main() {
  ll n, k, m;
  scanf("%lld%lld%lld", &n, &k, &m);
  vector<item> items(2*n);
  vector<bool> bought(n, false);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &items;[i].price, &items;[i+n].price);
    items[i].id = items[i+n].id = i;
    items[i].not_discounted = 0;
    items[i+n].not_discounted = items[i].price;
    items[i].discounted = false;
    items[i+n].discounted = true;
  }
  sort(items.begin(), items.end());
  int ans = 0;
  ll spent = 0;
  for (int i = 0; i < 2*n; i++) {
    if (items[i].price + spent <= m) {
      if (!bought[items[i].id]) {
        if (items[i].discounted) {
          if (k) {
            k--;
          } else {
            continue;
          }
        }
        spent += items[i].price;
        bought[items[i].id] = true;
        ans++;
      }
    }
  }
  cout<<ans<<endl;
  return 0;
}

stevenfan@stevenfan usaco $  make coupons
make: `coupons' is up to date.
stevenfan@stevenfan usaco $  for i in `seq 1 14`; do ./coupons < $i.in | diff -y - $i.out;done
3        3
2        2
12        12
125        125
614        614
2428        2428
1717        1717
15        15
9        9
6234        6234
15        15
433        433
0        0
5        5