Is the following problem decidable in polynomial time? We are given an initial set of tuples $S_0=\{(x_i,y_i)|i\in [n], \forall i:x_i,y_i\in \mathbb{N}\}$ and a number $B\in \mathbb{N}$.

At time $t$ we are allowed to remove ($S_t := S_{t-1} \setminus \{(x_i,y_i)\}$) 

a pair $(x_i,y_i)\in S_{t-1}$:  if $$x_i + \Sigma_{j:(x_j,y_j)\in S_{t-1}, j\neq i} y_j \geq B$$.

(That is if the sum of $x_i$ and the rest of the $y_j$'s is at least $B$ we're allowed to remove tuple $i$).

The problem is finding a sequence of tuples which can be legally removed, and leave a minimal cardinality set (i.e. remove as many tuples as possible).

Is this problem in $P$ as it is?

What if we know that $\forall i:y_i\leq x_i$?



Example: Assume $S_0 = \{(5,3),(5,5),(1,1),(6,0),(2,2)\}, B=10$ then $(&lt;1,1&gt;,&lt;6,0&gt;,&lt;2,2&gt;,&lt;5,3&gt;)$ is an example of a maximal output sequence.
This is a nice exercise, such as one might find in an undergrad-level algorithms class.  (Congratulate your professor on selecting such a nice exercise.)  Since it's your exercise, I'm going to let you solve it, but I'll give you a series of hints.

Important: Spend at least an hour exploring each hint, before moving on to the next hint.



Hint #1:


  When given an algorithms problem, it is often very helpful to look at some small examples and work out what's going on by hand.
  
  So, pick a sample problem instance with 3 items (generate the $x_i,y_i$'s arbitrarily); map out all possible timelines (all possible sequences of item removals); and see what you see.  Do another example with 3 items.  Try one with 4 items.  Do a few such examples, and see if you can build some intuition.  I suspect you'll spot what is going on, and then from that you might be able to figure out how to solve the problem.




Hint #2:


   What chapter of the textbook are you currently in?  This is often a good heuristic to help you select a type of algorithm to try.




Hint #3:


   A natural algorithmic approach is to use a greedy algorithm: if multiple items are currently eligible for removal, select the item whose $y_i$ value is _____.  (You fill in the blank.)  So, see if you can determine whether you can find any way to fill in the blank that provides a correct algorithm for your problem.  This gives you a few candidate algorithms; for each candidate, see if you can prove or disprove its correctness.  To do that, try some small examples.  See if you can find a proof of correctness or a counterexample demonstrating it is incorrect.  Once you've worked out whether there is any algorithm of this form that is correct, you should be able to answer your question.




Hint #4:


   If you've tried all of the above diligently, show us your work and where you got stuck and I'll give you one more hint.