Codeforces•Sep 08, 2025

Block Adventure

Hazrat Ali

Codeforces

Gildong plays the game as a character that can stand only on the top of the columns. At the beginning, the character is standing on the top of the 1-st column. The goal of the game is to move the character to the top of the n-th column.

The character also has a bag that can hold infinitely many blocks. When the character is on the top of the i-th column, Gildong can take one of the following three actions as many times as he wants:

  • if there is at least one block on the column, remove one block from the top of the i-th column and put it in the bag;
  • if there is at least one block in the bag, take one block out of the bag and place it on the top of the i-th column;
  • if i<n and |hi−hi+1|≤k, move the character to the top of the i+1-st column. k is a non-negative integer given at the beginning of the game. Note that it is only possible to move to the next column.

In actions of the first two types the character remains in the i-th column, and the value hi changes.

The character initially has m blocks in the bag. Gildong wants to know if it is possible to win the game. Help Gildong find the answer to his question.

Input

Each test contains one or more test cases. The first line contains the number of test cases t (1≤t≤1000). Description of the test cases follows.

The first line of each test case contains three integers n, m, and k (1≤n≤100, 0≤m≤106, 0≤k≤106) — the number of columns in the game, the number of blocks in the character's bag at the beginning, and the non-negative integer k described in the statement.

The second line of each test case contains n integers. The i-th integer is hi (0≤hi≤106), the initial height of the i-th column.

Output

For each test case, print "YES" if it is possible to win the game. Otherwise, print "NO".

You can print each letter in any case (upper or lower).

Example
Input
5
3 0 1
4 3 5
3 1 2
1 4 7
4 10 0
10 20 10 20
2 5 5
0 11
1 9 9
99
Output
YES
NO
YES
NO
YES

Solution

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

int main()
{

    int t;
    cin >> t;
    while (t--)
    {
        long long n, m, k;
        cin >> n >> m >> k;
        vector<long long> h(n);
        for (int i = 0; i < n; i++)
        {
            cin >> h[i];
        }
        bool win = true;
        for (int i = 0; i < n - 1; i++)
        {
            long long cur = h[i];
            long long nxt = h[i + 1];
            if (cur < nxt)
            {
                if (cur + m + k < nxt)
                {
                    win = false;
                    break;
                }
                else
                {
                    m -= nxt - cur - k;
                }
            }
            else
            {
                m += min(cur, cur - nxt + k);
            }
        }
        if (win)
        {
            cout << "YES" << endl;
        }
        else
        {
            cout << "NO" << endl;
        }
    }
    return 0;
}




Comments