You are attacked by a set of N monsters in a game. You have to design an algorithm to calculate the maximum number of these you could kill, adhering to the constraints below. 1) You begin with B units of initial energy. 2) To kill a monster n (1<=n<=N), you need to spend Kn units of energy out of your reserve. After monster is killed, you would gain Gn units of energy in return. 3) At any point, if your energy goes down to 0, you can no more kill any of the remaining ones and you stop at that point.
INPUT : B N K1 G1 K2 G2 . . KN GN
Where
B = initial energy you being with(B<100) N = total number of monsters (N<10000) followed by N lines in the form Kn = energy needed to kill monster n(1<=n<=N) Gn = energy gained after killing monster n(1<=n<=N) These N lines for the K and G values are not sorted in anyway, i.e neither on ASC/DESC order of K, nor on G.
OUTPUT : M = maximum number of monsters that can be killed
Provide a C/Java implementation of the function with appropriate method/function signature (any other language or pseudocode also works)