綾はショッピングモールをぶらぶらしており、一台のガチャガチャ（扭蛋機）が彼女の目を引きました。 このガチャガチャには $n$ 種類の景品が入っており、$i$ 種類目の景品は $a_i$ 個あります。

• ガチャコインを1枚消費すると、景品をランダムに1つ獲得できます。
• 任意の景品を $k$ 個消費すると、指定コイン（指定币）1枚と交換できます。
• 指定コインを1枚消費すると、ガチャガチャの中にある指定した種類の景品を1つ獲得できます。

一度出た景品がガチャガチャに戻されることはありません。 綾は $n$ 種類すべての景品を集めたいと考えています。つまり、最終的に各種類の景品を少なくとも1つずつ持っている状態を目指します。$n$ 種類すべての景品を確実に集めるために必要なガチャコインの最小枚数を求めてください。

入力

入力は複数のテストケースから構成されます。1行目に正整数 $T$ ($1 \le T \le 3000$) が与えられ、データセットの数を示します。 各データセットは以下の形式で与えられます。

1行目に2つの正整数 $n, k$ ($1 \le n \le 3000, 1 \le k \le 3 \times 10^5$) が与えられ、それぞれ景品の種類数と指定コインへの交換に必要な景品数を表します。 2行目に $n$ 個の正整数が与えられ、$i$ 番目の整数 $a_i$ ($1 \le a_i \le 3000$) は $i$ 種類目の景品の個数を表します。

すべてのテストケースにおける $n$ の総和は 3000 を超えません。

出力

各データセットについて、$n$ 種類すべての景品を確実に集めるために必要なガチャコインの最小枚数を1行で出力してください。

入出力例

入力 1

2
2 2
1 4
4 3
8 7 6 5

出力 1

3
9