Hi community,

I've been thinking about some problem for a while, and was wondering if it has a polynomial time solution. The problem goes as follows:

You character starts with B blue tickets and R red tickets. There are N offers proposed to you, the i'th in which you first lose a_i blue tickets, b_i red tickets, and then right afterwards gain c_i blue tickets and d_i red tickets (Suppose all values except N are  ≤ 10⁹). You lose if you ever have a negative amount of either ticket type. Is it possible to complete all offers and not lose?

Obviously you first want to complete all offers that yield positive profit for both red and blue tickets, but even then there might be some offers you can't complete. The rest is not so trivial.

Does anyone have ideas or seen this problem before? As said, this is original, so I don't have a problem link and am simply looking for the best time complexity possible.