Social Distance
Contest: Codeforces Round 783 (Div. 2)
Difficulty rating: 900
Tags: greedy, math, sortings

$$$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.

Input format:
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 format:
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).

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

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.

Example input:
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

Example output:
NO
YES
NO
YES
NO
YES

Editorial:
If there is no one between the $$$i$$$-th and $$$j$$$-th person then $$$max(a_i, a_j)$$$ free chairs should be between them. So we should find a permutation $$$p$$$ of the array $$$a$$$, when $$$max(p_1, p_2)+max(p_2, p_3) ... +max(p_{n-1}, p_n)+max(p_n, p_1)$$$ is minimal.
We can assume that the array is non-decreasing ($$$a_i \leq a_{i+1}$$$). For each $$$i$$$ ($$$1≤i<n$$$) the $$$i$$$ largest elements from $$$a$$$ ($$$a_{n-i+1}$$$ ... $$$a_n$$$) will appear in at least $$$i+1$$$ segments. Every element occurs twice, and we only can count $$$i-1$$$ segments twice. So we get a lower bound for the number of free chairs: $$$a_2+a_3+...+a_{n-1}+2 \cdot a_n$$$.
This lower bound is reachable for the empty chairs if the permutation of $$$p$$$ is sorted. Because $$$max(p_1, p_2)=p_2$$$, $$$max(p_2, p_3)=p_3$$$, ... $$$max(p_{n-1}, p_n)=p_n$$$, and $$$max(p_n, p_1)=p_n$$$.
They also sit on $$$n$$$ chairs. If we add all of these, we get that the answer is "YES" if: $$$n+ \sum_{i=1}^{n}(a_i)-min(a_i)+max(a_i)≤m$$$. ($$$a_i$$$={$$$a_1, a_2, ... a_n$$$})