Social Distance

题意翻译

### 题目描述 有一圈共 $m$ 个座椅（编号 $0 \sim m-1$），有 $n$ 个人要坐在上面，第 $i$ 个人左右两边至少要有 $a_i$ 个空座椅，问是否有一种方案可以使得所有人都能坐在上面。 ### 输入格式 第一行一个整数 $t ( 1\le t \le 5 ⋅ 10^4 )$，表示有 $t$ 组询问。 接下来 $2⋅t$ 行，每两行为一组询问。对于每一组询问，第一行两个整数，为 $n$ 和 $m$ ($2\le n \le 10^5$, $1\le m \le 10^9$)，接下来一行为 $n$ 个整数，第 $i$ 个整数为 $a_i(1\le a_i \le 10^9 )$。 ### 输出格式 对于每一组询问，输出对应的答案，可以输出 `YES`，否则输出 `NO`。 ### 说明/提示 样例第一组询问：人数大于座椅数，无解。 样例第二组询问：一种可行解为第一个人坐编号为 $2$ 的座椅，第二个人坐编号为 $0$ 的座椅。 样例第三组询问：第二个人无论坐哪，第一个人都没有位置，无解。 样例第四组询问：一种可行解为第一个人坐编号为 $1$ 的座椅，第二个人坐编号为 $4$ 的座椅，第三个人坐编号为 $7$ 的座椅。

题目描述

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

输入输出样例

输入样例 #1

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

输出样例 #1

NO
YES
NO
YES
NO
YES

说明

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.