Magic Task Completion

You are given an initial time T and n magic tasks. The i-th task can only be performed if your current time T is strictly greater than a given threshold \(t_i\). Completing a task does not consume time; however, upon finishing task \(i\), your time increases by \(b_i\) (i.e. \(T \gets T + b_i\)). At every moment, your time must remain positive (i.e. \(T>0\)). Determine whether it is possible to complete all \(n\) tasks in some order. If it is possible, output +1s; otherwise, output -1s.

Note: The tasks can be performed in any order. In order to solve the problem, one common approach is to separate the tasks into two groups: those with non-negative \(b_i\) (safe tasks) and those with negative \(b_i\) (dangerous tasks). The safe tasks are best done first in increasing order of \(t_i\) because they only increase your time. The dangerous tasks are handled later and are sorted in descending order of \(t_i + b_i\) to minimize the risk of dropping \(T\) to 0 or below.

inputFormat

The first line contains two integers \(n\) and \(T\) separated by space, where \(n\) is the number of magic tasks and \(T\) is your initial time.

Each of the next \(n\) lines contains two integers \(t_i\) and \(b_i\) representing the requirement and bonus for the \(i\)-th task.

Note that you can perform the tasks in any order.

outputFormat

If it is possible to complete all tasks while keeping \(T>0\) at all times, output +1s. Otherwise, output -1s.

sample

3 10
5 4
6 -5
8 -8

+1s