题目描述

真是忙碌的一周！这个周末，将会有 $n$ 场程序设竞赛同时进行。

每场竞赛将会从每 $k$ 支参加该竞赛的队伍中颁发一枚金牌。也就是说，如果有 $t$ 支队伍参加竞赛，将会颁发 $\lfloor \frac{t}{k} \rfloor$ 枚金牌，其中 $\lfloor x \rfloor$ 是不超过 $x$ 的最大整数。目前第 $i$ 场竞赛有 $a_i$ 支队伍参加。

堡堡是一所大学的教练，该大学有 $m$ 支队伍，并且他还没有决定每支队伍应该参加哪场竞赛。请帮助他为每支队伍分配一场竞赛，使得所有竞赛颁发的金牌总数最多。

输入格式

有多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 100$）表示测试数据组数，对于每组测试数据：

第一行输入两个整数 $n$ 和 $k$（$1 \le n \le 100$，$1 \le k \le 10^9$），表示竞赛的数量和金牌的比例。

第二行输入 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le 10^9$），其中 $a_i$ 表示目前有几支队伍参加第 $i$ 场竞赛。

第三行输入一个整数 $m$（$1 \le m \le 10^9$），表示您需要为多少支队伍安排竞赛。

输出格式

每组数据输出一行一个整数，表示所有竞赛最多一共颁发多少金牌。

2
3 10
239 141 526
6
2 1
300 100
1000

91
1400

提示

对于第一组样例数据，派 $2$ 支队伍去第 $1$ 场竞赛，$4$ 支队伍去第 $3$ 场竞赛。金牌总数为 $\lfloor \frac{239 + 2}{10} \rfloor + \lfloor \frac{141 + 0}{10} \rfloor + \lfloor \frac{526 + 4}{10} \rfloor = 24 + 14 + 53 = 91$。