「LAOI-17」上海紅茶館
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

\hspace{15pt}现在有 n 个商品从左往右排成一排，对于第 i 个商品，其原价格为 a_i，且商家可以至多进行 c_i 次涨价，每次涨价可以将其价格增加 b_i。但是，商家对于所有商品最多只能进行 k 次涨价。
\hspace{15pt}商家认为这一排商品的「价值」通过如下方式得到：
\hspace{23pt}\bullet\,在所有涨价完成后，商家可以将连续的一些商品（至少两个）捆绑起来销售，成为一个捆绑商品；
\hspace{23pt}\bullet\,每个商品至多被捆绑一次，或不被捆绑；
\hspace{23pt}\bullet\,将这些捆绑商品的平均价格从大到小排序，令这一排商品的「价值」为第三个平均价格（不去重，即非严格第三大）。因此商家至少准备三个捆绑商品。
\hspace{15pt}现查询在所有涨价与捆绑销售方案中，这一排商品的「价值」最大可能是多少。

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leq T\leq 100\right) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}第一行输入两个整数 n,k\left(6\le n\le 2\times10^5;\,1\le k \le 10^9\right)，表示初始商品个数、涨价次数。
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n\left(1\le a_i\le 10^9\right)。 
\hspace{15pt}第三行输入 n 个整数 b_1,b_2,\dots,b_n\left(1\le b_i\le 10^9\right)。 
\hspace{15pt}第四行输入 n 个整数 c_1,c_2,\dots,c_n\left(1\le c_i\le 10^9\right)。

\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 2\times 10^5。

输出描述:

\hspace{15pt}对于每一组测试数据，新起一行。可以证明答案可以表示为一个不可约分数 \frac{p}{q}，为了避免精度问题，请直接输出 p 和 q，中间使用一个斜杠隔开。例如 \tfrac{5}{3}、\tfrac{2}{4}、-1、0、1 应分别输出 5/3、1/2、-1/1、0/1、1/1。
示例1

输入

复制 
3
6 1
29166 37092 64023 97432 6879 68934
79327 73422 35664 14201 3117 38297
33311 22420 80684 84882 75019 64802
6 2
68310 98974 68618 29656 97060 39974
72840 70613 61869 52302 37203 42784
60686 83667 36977 83628 87067 90471
6 3
2005 51914 33818 43112 1833 12300
33836 88240 53047 5587 22524 56278
8500 55611 71388 79051 14030 52013

输出

复制 
75813/2
160143/2
38465/1

说明

\hspace{15pt}对于第一组测试数据，可以先将商品 2 涨价一次，然后将 1,2 和 3,4 和 5,6 商品分别捆绑销售，则 5,6 商品的组合为第三大平均价格，故价值为 75813/2。不难发现此为最优方案。
示例2

输入

复制 
3
12 9
79527 40058 51839 51493 887 4469 57411 96353 95414 47201 18007 40490
64995 20975 72275 31838 40050 61452 89477 2443 70645 53339 75382 24690
2 2 4 2 5 5 3 1 4 5 2 1
12 10
21728 765 41905 61950 48829 92058 61704 11982 22343 50498 43114 89406
41850 6264 2677 69207 38503 66063 14660 49741 22564 95718 5942 64791
5 1 4 1 4 5 4 4 5 4 2 2
12 3
55765 1963 1526 86230 18380 92101 87588 59877 38353 15731 50731 49499
25205 81169 9346 51883 38723 6457 97018 77175 5812 19407 92019 50607
3 1 1 3 1 2 2 3 1 1 1 3

输出

复制 
166359/1
295495/2
179689/2