You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

已经没有人能够阻止神仙了！

But，现在又出现了N个行踪诡秘的幻影长矛手。所有幻影长矛手身形一致，一字排开，只有击倒其中的K个，才能终结他们。

幸好神仙利用超乎想象的第七感，感受到了N个幻影长矛手的血量分别为Ai，但是由于幻影的能量过于强盛，连神仙也没能将N个幻影的血量与他们相对应上。

现在神仙每次能在$10^{-100}$s的时间里对一个单位造成一点伤害，他想知道在他的神仙操作下最少需要进攻多少次（即最优策略在最坏情况下）。

Format

Input

一行一个正整数T，表示神仙面临了T队幻影长矛手

接下来对于每组数据：

​ 一行两个正整数N，K，意义如上

​ 接下来一行N个正整数Ai，意义如上

Output

T行每行一个整数表示最少进攻数

Samples

2
2 1
50 55 
2 1
40 100

55
80

Explanation

• 第一个样例显然只要硬怼一个，最坏情况下只要进攻55
• 第二个样例显然只要找一个先试打40下，最坏情况下（即打在了100这个大坦克上）换一个再打40，所以只需80

Limitation

T<=10，0<K<=N<=1000, Ai<=$10^{9}$