Solution Notes: If there were no coupon, this problem would be solved by "greedily" using gifts in increasing order of P+S values (since we want to pack in as many gifts as possible before we hit the budget). In fact, if we know the gift to which we want to apply the coupon, the rest of our budget should be filled this same way -- by purchasing the remaining gifts "greedily" in increasing order of P+S. A simple solution now is to just try every possible gift as the "coupon" gift (greedily purchasing any remaining gifts that fit), and taking the best solution. The code below does this in O(N^2) time, which is plenty fast for the limits in this problem. As an exercise, can you figure out how to solve it in only O(N log N) time?

[Note: This solution has been modified since it was originally posted to correct a bug.]

#include <stdio.h>
#define MAX_N 1000

int N, B, P[MAX_N], S[MAX_N];

void sort_by_p_plus_s(void)
{
  int i, tmp, done=0;

  while (!done) {
    done = 1;
    for (i=0; i<N-1; i++)
      if (P[i]+S[i] > P[i+1]+S[i+1]) {
        tmp = P[i]; P[i] = P[i+1]; P[i+1] = tmp;
        tmp = S[i]; S[i] = S[i+1]; S[i+1] = tmp;
        done = 0;
      }
  }
}

int try_coupon(int c)
{
  int i, budget = B - (P[c]/2+S[c]), total=1;

  if (budget < 0) return 0;

  for (i=0; i<N; i++) 
    if (P[i]+S[i] <= budget && i!=c) {
      budget -= P[i]+S[i];
      total++;
    }

  return total;
}

int main(void)
{
  int i, best=0;

  freopen ("gifts.in", "r", stdin);
  freopen ("gifts.out", "w", stdout);

  scanf ("%d %d", &N, &B);
  for (i=0; i<N; i++)
    scanf ("%d %d", &P[i], &S[i]);

  sort_by_p_plus_s();

  for (i=0; i<N; i++)
    if (try_coupon(i) > best) 
      best = try_coupon(i);

  printf ("%d\n", best);
  
  return 0;
}