午餐后，Vasya 和 Petya 的口袋里通常装满了找零得到的硬币。因此，他们喜欢玩以下游戏。

他们将硬币按某种顺序排成一行，然后轮流进行操作。每次操作，玩家可以选择：

• 从最左侧开始取走连续的若干枚硬币；
• 从最右侧开始取走连续的若干枚硬币；
• 选择一个整数 $d$ ($d > 1$)，保留每一枚第 $d$ 个硬币（即位置为 $d, 2 \cdot d, 3 \cdot d, \dots$ 的硬币，从最左侧开始计数），并取走其余所有硬币。

当没有硬币剩下时，游戏结束。每位玩家的目标是最大化自己取走的金额。

按照这些规则进行的游戏通常结束得太快，因此玩家们增加了一个限制：在一次操作中，取走的硬币总金额不能超过某个指定的限额。

Vasya 和 Petya 排好了所有的硬币。请帮助他们确定，如果双方都采取最优策略，且 Vasya 先手，最终每人各能得到多少金额。

请注意，Vasya 和 Petya 使用的是现代俄罗斯硬币。提醒一下，在俄罗斯，流通的硬币面额为 1, 5, 10, 50, 100（1 卢布）, 200（2 卢布）, 500（5 卢布）和 1000 戈比（10 卢布）。

输入格式

输入包含多个测试用例。第一行包含测试用例的数量 $T$ ($1 \le T \le 20$)。接下来是各个测试用例。

每个测试用例由两行组成。第一行包含两个整数 $N$ 和 $M$ ($1 \le N \le 250, 1000 \le M \le 10\,000$)：表示排成一行的硬币数量以及单次操作的金额上限（单位为戈比）。第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N$，其中每个数均属于 $\{1, 5, 10, 50, 100, 200, 500, 1000\}$。

所有测试用例的 $N$ 之和不超过 1000。

输出格式

对于每个测试用例，输出一行，包含两个数字：在双方均采取最优策略的情况下，Vasya 和 Petya 分别获得的戈比金额。

样例

输入 1

3
5 1000
1 1 1 1 1
8 1000
1 1000 1 1000 10 1000 5 1000
5 1000
1 1000 5 1000 10

输出 1

5 0
3000 1017
1016 1000