题目背景

哪吒又去降妖除魔了~

题目描述

哪吒原有 $s$ 的武力值。现在共有 $T$ 处妖怪，每处有 $n$ 只妖怪，其中最后一只是“妖王”（Boss），每解决一只妖王就会获得 $k$ 的武力值。

每只小妖有 $a_i$ 的武力值，如果这只小妖的武力值小于哪吒的武力值，则哪吒可以直接解决这只小妖（不需要耗费武力值）；否则，哪吒将被打败。

每只妖王有 $a_n$ 的武力值，如果这只妖王的武力值小于哪吒的武力值，则哪吒可以直接解决这只妖王（需要耗费武力值，但可以获得 $k$ 的武力值）；否则，哪吒将被打败。

输入格式

输入的第一行包含两个整数 $T$ 和 $s$

接下来包含 $T$ 组数据，每组数据格式如下：

第一行包含两个整数，分别是 $n$ 和 $k$

第二行包含 $n$ 个整数，分别是 $a_i$

输出格式

如果哪吒能打赢 $T$ 处的所有妖怪，则输出最后的武力值；否则则输出在第几处哪吒会被打败

输入输出样例 #1

输入 #1

1 11
6 4
1 1 4 4 2 10

输出 #1

5

说明/提示

对于 $25\%$ 的数据，保证 $1 \leq n \leq 10^2$,

对于 $50\%$ 的数据，保证 $1 \leq n \leq 10^3$,

对于 $100\%$ 的数据，保证

$1 \leq n \leq 10^4$,

$1\leq a_i,k,s \leq 10^9$

$1\leq T \leq 10^2$