Chơi Minecraft

Bối cảnh

Hưng đang chơi một tựa game có tên Minecraft. Trong game này, có \(n\) cột khối được dựng thành một hàng, các cột được đánh số từ \(1\) đến \(n\). Mỗi khối có độ cao bằng nhau. Độ cao của cột thứ \(i\) được biểu diễn là \(h_i\), tương ứng với số lượng khối được chồng ở cột thứ \(i\).

Yêu cầu

Trong trò chơi, Hưng đang đóng vai nhân vật Steve chỉ có thể đứng trên đỉnh của một khối bất kì. Ban đầu, Steve đứng ở đỉnh của cột thứ nhất (cột \(1\)). Hưng muốn nhân vật của mình đi đến đỉnh của cột cuối cùng (cột \(n\)).

Bên cạnh đó, Steve còn có một chiếc túi có khả năng chứa đựng vô hạn khối. Khi nhân vật đứng ở đỉnh thứ \(i\), Hưng có thể thực hiện một trong ba thao tác sau:

• Nếu có ít nhất một khối trên cột hiện tại, lấy một khối trên đỉnh của cột và cho nó vào túi. Khi đó \(h_i = h_i - 1\) (chiều cao của cột hiện tại giảm đi \(1\) đơn vị).
• Nếu có ít nhất một khối trong túi, lấy khối đó ra và đặt lên trên đỉnh của cột hiện tại. Khi đó, \(h_i = h_i + 1\) (chiều cao của cột hiện tại tăng thêm \(1\) đơn vị).
• Nếu \(i < n\) và \(h_i = h_{i+1}\), di chuyển nhân vật đến đỉnh của cột thứ \(i+1\).

Biết rằng ban đầu trong túi của Steve có \(m\) khối. Hãy giúp Hưng thực hiện thử thách của trò chơi và giành chiến thắng.

Input

Dòng đầu tiên một số nguyên \(t\ (1\leq t\leq 1000)\) cho biết số test. Mỗi test có hai dòng.

Dòng thứ nhất của mỗi test chứa hai số nguyên \(n\) và \(m\) \((1\leq n\leq 100, 0\leq m\leq 10^6)\) - số cột khối trong trò chơi và số lượng khối ở trong túi của Steve ban đầu.

Dòng thứ hai của mỗi test chứa \(n\) số nguyên \(h_1, h_2,..., h_n\ (0\leq h_i\leq 10^6)\) - chiều dài ban đầu của các cột khối.

Output

Với mỗi testcase, in ra YES nếu bạn có thể giúp Hưng hoàn thành thử thách của trò chơi. Ngược lại in ra NO.

Ràng buộc

Đề gốc không nêu ràng buộc riêng.

Ví dụ 1

Input

3
4 0
4 2 2 5
4 1
4 2 2 5
4 2
3 0 1 4

Output

NO
YES
YES

Giải thích ví dụ

• Ở test thứ nhất, Hưng lấy hai khối từ cột \(1\) (số khối trong túi Steve là \(0 + 2 = 2\)), di chuyển sang cột \(2\), di chuyển sang cột \(3\). Tuy nhiên không thể di chuyển tiếp sang cột \(4\) vì cần đặt \(3\) khối lên đỉnh cột \(3\) để \(h_i = h_{i+1}\) mà trong túi của Steve chỉ có \(2\) khối.
• Ở test thứ hai, Hưng lấy hai khối từ cột \(1\) (số khối trong túi Steve là \(1 + 2 = 3\)), di chuyển sang cột \(2\), di chuyển sang cột \(3\). Sau đó đặt \(3\) khối từ trong túi lên đỉnh cột \(3\) (số khối trong túi Steve là \(3 - 3 = 0\)) và di chuyển sang cột \(4\).
• Ở test thứ ba, Hưng lấy ba khối từ cột \(1\) (số khối trong túi Steve là \(2 + 3 = 5\)), di chuyển sang cột \(2\), đặt \(1\) khối từ trong túi lên cột \(2\) (số khối trong túi Steve là \(5 - 1 = 4\)), di chuyển sang cột \(3\), đặt \(3\) khối từ trong túi lên cột \(3\) (số khối trong túi Steve là \(4 - 3 = 1\)), di chuyển sang cột \(4\).

Thông tin học tập

• Buổi: B04
• Concepts: loops, state simulation, conditionals
• Giới hạn kiến thức: B01-B04
• Time limit: 1 second
• Memory limit: 20 MB
• Point: 20