codeforces#P1668B. Social Distance
Social Distance
Description
$m$ chairs are arranged in a circle sequentially. The chairs are numbered from $0$ to $m-1$. $n$ people want to sit in these chairs. The $i$-th of them wants at least $a[i]$ empty chairs both on his right and left side.
More formally, if the $i$-th person sits in the $j$-th chair, then no one else should sit in the following chairs: $(j-a[i]) \bmod m$, $(j-a[i]+1) \bmod m$, ... $(j+a[i]-1) \bmod m$, $(j+a[i]) \bmod m$.
Decide if it is possible to sit down for all of them, under the given limitations.
The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 5 \cdot 10^4$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 10^5$, $1 \leq m \leq 10^9$) — the number of people and the number of chairs.
The next line contains $n$ integers, $a_1$, $a_2$, ... $a_n$ ($1 \leq a_i \leq 10^9$) — the minimum number of empty chairs, on both sides of the $i$-th person.
It is guaranteed that the sum of $n$ over all test cases will not exceed $10^5$.
For each test case print "YES" (without quotes) if it is possible for everyone to sit down and fulfil the restrictions, and "NO" (without quotes) otherwise.
You may print every letter in any case you want (so, for example, the strings "yEs", "yes", "Yes" and "YES" will all be recognized as positive answers).
Input
The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 5 \cdot 10^4$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 10^5$, $1 \leq m \leq 10^9$) — the number of people and the number of chairs.
The next line contains $n$ integers, $a_1$, $a_2$, ... $a_n$ ($1 \leq a_i \leq 10^9$) — the minimum number of empty chairs, on both sides of the $i$-th person.
It is guaranteed that the sum of $n$ over all test cases will not exceed $10^5$.
Output
For each test case print "YES" (without quotes) if it is possible for everyone to sit down and fulfil the restrictions, and "NO" (without quotes) otherwise.
You may print every letter in any case you want (so, for example, the strings "yEs", "yes", "Yes" and "YES" will all be recognized as positive answers).
Samples
6
3 2
1 1 1
2 4
1 1
2 5
2 1
3 8
1 2 1
4 12
1 2 1 3
4 19
1 2 1 3
NO
YES
NO
YES
NO
YES
Note
Test case $1$: $n>m$, so they can not sit down.
Test case $2$: the first person can sit $2$-nd and the second person can sit in the $0$-th chair. Both of them want at least $1$ empty chair on both sides, chairs $1$ and $3$ are free, so this is a good solution.
Test case $3$: if the second person sits down somewhere, he needs $2$ empty chairs, both on his right and on his left side, so it is impossible to find a place for the first person, because there are only $5$ chairs.
Test case $4$: they can sit in the $1$-st, $4$-th, $7$-th chairs respectively.