Background

王权对权王不让权王权王权这件事积怨已久。为此，一场激烈的对决即将爆发……

Description

小W 和小Q 有一些特殊的石子，他们打算玩取石子游戏。他们一共有n 颗石子，这些石
子样式各异，每颗石子都有自己的美观程度bi 和权值 wi。在游戏进行的过程中，场上的石子
会不断被取走；而场上剩下的石子的数目所对应的小W 和小Q 的关注程度越高，比赛在那个
时刻的紧张程度就越高。为简便起见，我们定义一个将石子数目映射到双方关注程度之和的函
数c(x)。约定c（0）=0。
这样美丽的石子总是让人赏心悦目的。然而，当局面进展到关键情形（场上石子的权值和
与关注程度和的乘积大于场上石子的美观程度和与场上石子数目的乘积）时，对局的紧张气氛
将加剧。由于小Q 比小W 来得Q，因此小Q 只有在这一情况下才能得到一定的分数。
在此基础上，游戏的流程是：每轮先由小W 移除若干石子并以剩余权值和作为得分，再
由小Q 进行一次移除尝试，试图满足其得分条件。如果条件被满足则小Q 获得剩余权值和的m
倍作为得分（m 是剩余石子数），然后放回小Q 移除的石子，如此循环直至石子被取空。
更加具体且形式化地，这场游戏的流程如下：
1.开始时把所有石子置入场内，双方初始分数均为0。
2.小W 从场上石子中移除任意个（不可以移除0 个）。移除后，小W 获得∑wi 分。（求
和等计算均针对仍留在场上的石子，下同）
3.小Q 从场上石子中移除任意个（可以移除0 个）。移除后，设场上还剩m 个石子，如
果∑m·bi< ∑ c (m )·wi 成立，小 Q 获得∑ m ·wi 分。然后无论小 Q 是否获得了分数，
均将小Q 移除的石子移回。

Format

Input

输入的第1 行包含2 个整数n 和case ，n 表示石子的数量，case 表示测试点编号。
接下来1行，包含n 个整数，其中第i 个表示bi。
接下来1 行，包含n 个整数，其中第i 个表示wi。
接下来1行，包含n 个整数，其中第i 个表示c(i)的值。约定c（0）=0。

Output

输出一行2 个整数，依次表示双方均按最优策略行动时大W 和大Q 的最终得分。

Sample 1

Input

4 3
1 2 3 4
4 3 2 1
1 2 3 4

Output

50
【样例1 说明】
第1轮：大W移除1 号和2号石子（按输入顺序编号），得到 w3+w4=3分；可以证明，
该局面下大Q 无论如何行动均无法得分。注意此时大W 若移除4 号石子将得到更高的总分，
但大W 更希望最小化大Q 的分数（见题目描述），因此这里他不会选择移除4 号石子。
第2轮：大W移除4 号石子，得到 w3=2 分；大Q 仍然无法得分。
第3 轮：大W 移除3 号石子，游戏结束，大W 最终得分为5 分，大Q 最终得分为0 分。

Limitation