DLee 来到了一个新的关卡。等待他的是一座有 $n$ 层的高楼，每一层楼上都有一只怪物，其中第 $i$ 层怪物的生命值为 $a_i$。

DLee 从地面（可以看作第 $0$ 层）出发，初始攻击力为 $a_0$。他可以选择向上跳跃 $1, 2, \dots, k$ 层，或者向下走 $1$ 层。但他不能前往那些怪物生命值严格大于他当前攻击力的楼层，也不能前往已经访问过的楼层。一旦他到达某一层并击败了怪物，他就可以吸收该怪物的生命值，并将其加到自己的攻击力上。

注意，DLee 必须始终保持在 $\{0, 1, 2, 3, \dots, n\}$ 层之间。

现在 DLee 想问你，是否有可能击败所有的怪物并通关。

输入格式

输入包含 $T$ 组测试数据。

对于每组测试数据，第一行包含三个整数：$n, a_0, k$ ($1 \le n, k \le 10^5, 1 \le a_0 \le 10^9$)，分别表示楼层数、初始攻击力和 DLee 最多能向上跳跃的层数。

第二行包含 $n$ 个整数 $a_1, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示每只怪物的生命值。

所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出 "YES" 或 "NO"，表示是否可能击败所有怪物。

样例

样例输入 1

4
6 1 4
2 2 1 1 9 3
4 2 2
2 3 8 1
3 1 2
3 1 2
7 2 3
4 3 2 7 20 20 20

样例输出 1

YES
YES
NO
NO