Gildong is playing a video game called Block Adventure. In Block Adventure, there are $n$ columns of blocks in a row, and the columns are numbered from $1$ to $n$. All blocks have equal heights. The height of the $i$-th column is represented as $h_i$, which is the number of blocks stacked in the $i$-th column.

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 $|h_i - h_{i+1}| \le 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 $h_i$ 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 \le t \le 1000$). Description of the test cases follows.

The first line of each test case contains three integers $n$, $m$, and $k$ ($1 \le n \le 100$, $0 \le m \le 10^6$, $0 \le k \le 10^6$) — 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 $h_i$ ($0 \le h_i \le 10^6$), 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



-----Note-----

In the first case, Gildong can take one block from the $1$-st column, move to the $2$-nd column, put the block on the $2$-nd column, then move to the $3$-rd column.

In the second case, Gildong has to put the block in his bag on the $1$-st column to get to the $2$-nd column. But it is impossible to get to the $3$-rd column because $|h_2 - h_3| = 3 > k$ and there is no way to decrease the gap.

In the fifth case, the character is already on the $n$-th column from the start so the game is won instantly.

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
    n, m, k = list(map(int, input().split()))
    H = list(map(int, input().split()))
    ans = 'YES'
    for i in range(n - 1):
        h1 = H[i]
        h2 = H[i + 1]
        if h1 >= h2:
            if h2 >= k:
                m += (h1 - h2) + k
            else:
                m += h1
        else:
            if h2 > h1 + m + k:
                ans = 'NO'
                break
            elif h2 <= k:
                m += h1
            elif (h2 - h1) <= k:
                m += k - (h2 - h1)
            else:
                m -= h2 - h1 - k
    print(ans)


for __ in range(int(input())):
    n, m, k = map(int, input().split())
    arr = list(map(int, input().split()))
    flg = True
    for f, nx in zip(arr, arr[1:]):
        tg = max(nx - k, 0)
        m -= tg - f
        if m < 0: flg = False
    print('YES' if flg else 'NO')

def solve():
    n, m, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    for i in range(n - 1):
        if a[i] >= a[i + 1] - k:
            m += min(a[i], a[i] - max(a[i + 1] - k, 0))
            continue
        else:
            if a[i] + m < a[i + 1] - k:
                print('NO')
                return
            else:
                m -= max(0, a[i + 1] - k - a[i])
    print('YES')

t = int(input())

for _ in range(t):
    solve()


def main():
    import sys
    input = sys.stdin.readline
    
    def solve():
        n, m, k = map(int, input().split())
        arr = list(map(int, input().split()))
        
        curr = m
        for i in range(n - 1):
            diff = arr[i] - max(0, (arr[i + 1] - k))
            curr += diff
            if curr < 0:
                print("NO")
                return
        
        print("YES")
        return
    
    for _ in range(int(input())):
        solve()
    
    return 0

main()

for _ in range(int(input())):
    n, m, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    ok = 1
    for i in range(n - 1):
        lo = max(0, a[i + 1] - k)
        if a[i] > lo:
            m += a[i] - lo
        else:
            m -= lo - a[i]
        if m < 0:
            ok = 0
            break
    print('YES' if ok else 'NO')


t = int(input())

for _ in range(t):
	n, m, k = map(int, input().split())
	h = list(map(int, input().split()))

	possible = True
	cur_h = h[0]
	for next_h in h[1:]:
		if cur_h + k < next_h:
			needed = next_h - cur_h - k
			if needed > m:
				possible = False
				break
			m -= needed
		else:
			m += min(cur_h, cur_h - (next_h - k))
		cur_h = next_h

	if possible:
		print("YES")
	else:
		print("NO")

for t in range(int(input())):
    n,m,k = list(map(int,input().split()))
    h = list(map(int,input().split()))
    for i in range(n-1):
        if h[i]>=h[i+1]-k:
            m += h[i]-max(0,h[i+1]-k)
        else:
            if h[i]+m < h[i+1]-k:
                print('NO')
                break
            else:
                m -= h[i+1]-k-h[i]
    else:
        print('YES')


import sys
def input():
    return sys.stdin.readline()[:-1]

T = int(input())


for i in range(T):
    flag = True
    n,m,k = list(map(int,input().split()))
    h = list(map(int,input().split()))
    for i in range(n-1):
        x=max(h[i+1]-k,0)
        if x-h[i]>m:
            flag = False
            break
        else:
            m -= x-h[i]
    if flag:
        print("YES")
    else:
        print("NO")

def mp():
    return map(int, input().split())

t = int(input())

for tt in range(t):
    n, m, k = mp()
    a = list(mp())
    
    fail = False
    for i in range(n - 1):
        if a[i] >= a[i + 1]:
            m += min(a[i], a[i] - a[i + 1] + k)
        else:
            if abs(a[i + 1] - a[i]) <= k:
                m += min(a[i], a[i] - a[i + 1] + k)
            else:
                if m >= abs(a[i] - a[i + 1]) - k:
                    m -= abs(a[i] - a[i + 1]) - k
                else:
                    fail = True
                    break
    
    if fail:
        print('NO')
    else:
        print('YES')

t = int(input())
for _ in range(t):
    n, m, k = list(map(int, input().split()))
    h = list(map(int, input().split()))
    block = m
    flag = 1
    for i in range(n-1):
        if h[i+1]-k <= h[i]:
            block += min(h[i], h[i]-(h[i+1]-k))
        else:
            if h[i+1]-k-h[i] > block:
                flag = 0
                break
            else:
                block -= h[i+1]-k-h[i]
    if flag == 1:
        print("YES")
    else:
        print("NO")


from sys import stdin
t=int(stdin.readline().strip())
for case in range(t):
    n,m,k=list(map(int,stdin.readline().strip().split()))
    s=list(map(int,stdin.readline().strip().split()))
    t=True
    for j in range(n):
        if j!=n-1:
            x=(max(s[j]-max((s[j+1]-k),0),0))
            m+=(max(s[j]-max((s[j+1]-k),0),0))
            s[j]-=x
            
            y=max(max((s[j+1]-k),0)-s[j],0)
            m-=y
            if(m<0):
                t=False
            s[j]+=y

            if abs(s[j+1]-s[j])>k:
                t=False
    if t:
        print("YES")
    else:
        print("NO")


t = int(input())
for i in range(t):
	n, m, k = map(int, input().split())
	h = list(map(int, input().split()))
	for i in range(n - 1):
		if h[i] >= h[i+1] - k:
			m += min(h[i] - (h[i+1] - k), h[i])
		else:
			if m >= h[i+1] - k - h[i]:
				m -= h[i+1] - k - h[i]
			else:
				print('NO')
				break
	else:
		print('YES')

for t in range(int(input())):
    n,m,k=map(int,input().split())
    l=list(map(int,input().split()))
    dep=m
    for i in range(n-1):
        if l[i+1]>(l[i]+k):
            need=l[i+1]-(l[i]+k)
            if need>dep:
                print("NO")
                break
            dep-=need
        else:
            dep+=min(l[i],l[i]+k-l[i+1])
    else:
        print("YES")

t = int(input())

for _ in range(t):
    n, m, k = list(map(int, input().split()))
    h = list(map(int, input().split()))

    result = True
    for i in range(n - 1):
        if h[i + 1] - h[i] > k + m:
            result = False
            break
        elif h[i] + k > h[i + 1]:
            m += h[i] - h[i + 1] + min(k, h[i + 1])
        elif h[i + 1] > h[i] + k:
            m -= h[i + 1] - h[i] - k
            if m < 0:
                result = False
                break
        else:  # ==
            pass

    if result:
        print("YES")
    else:
        print("NO")


import sys
input = sys.stdin.readline

testcases=int(input())
for test in range(testcases):
    n,m,k=list(map(int,input().split()))
    H=list(map(int,input().split()))

    if n==1:
        print("YES")
        continue

    for i in range(n-1):
        if H[i]>H[i+1]-k:
            m+=min(H[i],H[i]-(H[i+1]-k))

        elif H[i]<H[i+1]-k:
            m-=(H[i+1]-k)-H[i]

        if m<0:
            print("NO")
            break

    else:
        print("YES")



t=int(input())
for _ in range(t):
  n,m,k=map(int,input().split())
  arr=list(map(int,input().split()))
  for i in range(n-1):
    if arr[i]<max(arr[i+1]-k,0):
      if m<max(arr[i+1]-k,0)-arr[i]:
        print('NO')
        break
      else:
        m-=max(arr[i+1]-k,0)-arr[i]
    else:
      m+=arr[i]-max(arr[i+1]-k,0)
  else:
    print('YES')

t = int(input())
for _ in range(t):
    n,m,k = map(int,input().split())
    h = list(map(int,input().split()))
    b = False
    for i in range(n-1):
        m += h[i] - max(h[i+1]-k,0)
        if m < 0:
            b = True
            break
    if b:
        print("NO")
    else:
        print("YES")

q=int(input())
for query in range(q):
    arr=[int(x) for x in input().split()]
    arr2=[int(x) for x in input().split()]
    n=arr[0]
    m=arr[1]
    k=arr[2]
    pos=True
    for i in range(n-1):
        l=arr2[i+1]-arr2[i]
        g=l-k
        t=max(g,-arr2[i])
        m-=t
        if m<0:
            pos=False
            break
    if pos==False:
        print("NO")
    else:
        print("YES")


import math
# helpful:
# r,g,b=map(int,input().split())
# arr = [[0 for x in range(columns)] for y in range(rows)]

t = int(input())
for i in range(t):
    possible = True
    n,m,k = list(map(int,input().split()))
    arr = input().split()
    for i in range(len(arr)):
        arr[i] = int(arr[i])
    maxBlocks = m
    for j in range(1, n):
        if(arr[j] - arr[j-1] > maxBlocks + k):
            possible = False
        else:
            if(arr[j-1] >= arr[j]-k):
                maxBlocks += min(arr[j-1] - max(arr[j] - k, 0), arr[j-1])
            elif(arr[j-1] < arr[j]-k):
                maxBlocks -= abs(arr[j] - arr[j-1]) - k
    if(possible):
        print("YES")
    else:
        print("NO")

    
                


for _ in range(int(input())):
    n, m, k = list(map(int, input().split()))
    hi = None
    for hi1 in map(int, input().split()):
        if hi is not None:
            m += hi
            if m + k < hi1:
                print("NO")
                break
            if hi1 > k:
                m -= hi1 - k
        hi = hi1
    else:
        print("YES")


t = int(input())
for i in range(t):
    n, m, k = list(map(int, input().split()))
    columns = list(map(int, input().split()))
    bag = m
    ok = True
    for i in range(n - 1):
        if columns[i + 1] - columns[i] > k:
            bag -= (columns[i + 1] - columns[i]) - k
            if bag < 0:
                ok = False
                break
        else:
            bag += columns[i] - max(0, columns[i + 1] - k)
    print('YES' if ok else 'NO')


def func(m, k, a):
    for i in range(len(a) - 1):
        if a[i] + k >= a[i + 1]:
            m += a[i] - max(0, a[i+1] - k)
        else:
            m = m - max(a[i + 1] - k - a[i], 0)
            if m < 0:
                return 0
    return 1


for _ in range(int(input())):
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    res=func(m, k, a)
    if res:
        print ("YES")
    else:
        print ("NO")