Codeforcess Solution 1473-A A. Replacing Elements ,C++, Java, Js and Python

Algorithm

You have an array $a_{1}, a_{2}, \dots, a_{n}$ . All $a_{i}$ are positive integers.

In one step you can choose three distinct indices $i$ , $j$ , and $k$ ( $i \neq j$ ; $i \neq k$ ; $j \neq k$ ) and assign the sum of $a_{j}$ and $a_{k}$ to $a_{i}$ , i. e. make $a_{i} = a_{j} + a_{k}$ .

Can you make all $a_{i}$ lower or equal to $d$ using the operation above any number of times (possibly, zero)?

Input

The first line contains a single integer $t$ ( $1 \leq t \leq 2000$ ) — the number of test cases.

The first line of each test case contains two integers $n$ and $d$ ( $3 \leq n \leq 100$ ; $1 \leq d \leq 100$ ) — the number of elements in the array $a$ and the value $d$ .

The second line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq 100$ ) — the array $a$ .

Output

For each test case, print YES, if it's possible to make all elements $a_{i}$ less or equal than $d$ using the operation above. Otherwise, print NO.

You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).

Example
input
Copy
3
5 3
2 3 2 5 4
3 4
2 4 4
5 4
2 1 5 3 6
output
Copy
NO
YES
YES

Note

In the first test case, we can prove that we can't make all $a_{i} \leq 3$ .

In the second test case, all $a_{i}$ are already less or equal than $d = 4$ .

In the third test case, we can, for example, choose $i = 5$ , $j = 1$ , $k = 2$ and make $a_{5} = a_{1} + a_{2} = 2 + 1 = 3$ . Array $a$ will become $[2, 1, 5, 3, 3]$ .

After that we can make $a_{3} = a_{5} + a_{2} = 3 + 1 = 4$ . Array will become $[2, 1, 4, 3, 3]$ and all elements are less or equal than $d = 4$ .

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;


#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int t;
  cin>>t;
  while(t--){
    int n, d;
    cin>>n>>d;
    int arr[n];
    for(int i = 0; i < n; i++){
      cin>>arr[i];
    }
    sort(arr, arr+n);
    if(arr[n-1] <= d){
      cout<<"YES"<<endl;
    }
    else if(arr[0] + arr[1] <= d){
      cout<<"YES"<<endl;
    }
    else{
      cout<<"NO"<<endl;
    }
  }

}

Copy The Code & Try With Live Editor

Input

–

cmd

3
5 3
2 3 2 5 4
3 4
2 4 4
5 4
2 1 5 3 6

Output

–

cmd

NO
YES
YES

Demonstration

Codeforcess Solution 1473-A A. Replacing Elements ,C++, Java, Js and Python,1473-A,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution

Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+

Try With Live Editor

Category - Codeforces Online Judge Maniruzzaman Akash 3 years ago 946 0