Description

After cjwssb realized it was a misunderstanding, he apologized to you. To cheer him up, you plan to start doing magic together. However, your time is running out, and worse, you still need to complete $n$ magic tasks. Suppose your current time is $T$. Each task has a constraint $t_i$, meaning you can complete this task only when your $T$ is strictly greater than $t_i$. Completing a task does not consume time. When you complete the $i$-th task, your time $T$ increases by $b_i$. At all times, $T$ must remain greater than $0$. Determine whether you can complete all $n$ magic tasks. If yes, output $\texttt{+1}\texttt{s}$; otherwise, output $\texttt{-1}\texttt{s}$.

Input Format

The first line contains an integer $Z$, the number of test cases.

For each test case:

• The first line contains two integers $n, T$, meaning there are $n$ tasks and your initial time is $T$.
• The next $n$ lines each contain two integers, $t_i$ and $b_i$.

Output Format

For each test case, output $\texttt{+1}\texttt{s}$ or $\texttt{-1}\texttt{s}$.

1
2 13
1 -9
5 -3

+1s

Hint

• For $20\%$ of the testdata, $n \leq 10$.
• For $100\%$ of the testdata, $n \leq 10^5$, $Z \leq 10$, $t_i \leq 10^5$, $T \leq 10^5$, $-10^5 \leq b_i \leq 10^5$.

By lantian.

$\LaTeX$ By ⚡炭治郎⚡.

Due to historical reasons, the blog discussion may not be able to post the sample output strings. You may consider other ways to work around this.

Translated by ChatGPT 5