Grant Wishes :
Difficulty Level : Medium
Submissions : 114
Asked In :
Marks :10
: 2 | : 2
Zasho is a popular genie.Being a genie, he's in the business of granting wishes, and a lot of people ask him for help. However, his power is limited - currently it is p units.
To grant the i-th wish, Zasho needs to have to have at least x units of power. After a wish is granted, his power rating changes by y (y can be positive or negative). His power should not dip below zero at any point.
Zasho wants to grant the maximum number of wishes possible so that he remains popular. Please help him figure this out.
In other words, find the maximum possible size of the subset of wishes so that Zasho has enough power before starting each, and has non negative power after completing each wish. Wish for the selected subset can be granted In any order.
First line contains two wishes n (1 <= n <= 100) and p (1 <= p <=30000). The next n lines contain the wishes, one per line. The I-th wish is represented as a pair of integers x and y (1 <= x <= 30000 , -300 <= y <= 300)
Output a single integer, the maximum size of the subset.
3 5 4 -5 4 -2 1 3
3
5 2 6 8 6 10 7 3 10 9 4 7
0
A possible order <2,3,1> exists.
