607. Project Completion

0

Medium

Polycarp, a renowned freelancer, possesses a current rating of r units. Several affluent clients have approached him to undertake projects for their respective companies. To successfully complete the i-th project, Polycarp must possess a minimum rating of ai units. Upon completion of this project, his rating will be altered by bi (either an increase or decrease). It is crucial for Polycarp's rating to remain non-negative, as a low rating would undermine his credibility. The task at hand is to determine if it is feasible to complete all the projects. In essence, you must develop a program to verify the existence of an order in which Polycarp can undertake the projects, ensuring that he possesses the required rating before commencing each project and maintains a non-negative rating after completing each project. Put simply, you need to ascertain if there exists an order of projects that allows Polycarp to complete them, ensuring he possesses the necessary rating before starting each project and maintains a non-negative rating after completing each project.

Input Format

The first line of input consists of two integers, n and r
These represent the number of projects and Polycarp's initial rating, respectively.
The subsequent n lines represent the projects, with each line containing a pair of integers, ai and bi
These integers denote the rating required to complete the i-th project and the subsequent rating change upon completion of the project.

Output Format

Print either "YES" or "NO".

Example

Input

3 4 4 6 10 -2 8 -1

Output

YES

Constraints

1≤n≤100,1≤r≤30000
1≤ai≤30000
−300≤bi≤300
Loading...

View Submissions

Console