题目描述

“河城杂货”开张啦！河城杂货店里现在有 $n$ 件货物，每件货物都有自己的固定价值 $a_i$ 。现在杂货店来了 $n+1$ 名顾客，每名顾客都有一个专属出价倍数 $b_i$ ，即他们购买一件货物时，实际出价为 “货物价值 × 自己的倍数 $b_i$ ”。

河城荷取一心想赚大钱，且至少要赚够 $m$ 元。她可以自由将任意一件货物卖给任意一名顾客，但一件货物仅能卖给一名顾客，一名顾客也最多购买一件货物。

荷取十分懒惰，却不愿放弃赚钱目标，为此她或许需要再进一件货物，所以请你帮她算出所需进货的最小价值 $v$ （ $v$ 的价格可以为任意正整数）；若不进货也能赚够至少 $m$ 元，输出 $0$ 即可。

输入格式

第一行一个正整数 $T$ 表示数据组数。

对于每组数据：

第一行包含两个整数 $n,m$ ，分别货物数量和想赚够的钱数。

第二行包含 $n$ 个空格分隔的整数 $a_1,a_2,…,a_n$ ，表示每件货物的价值。

第三行包含 $n+1$ 个空格分隔的整数 $b_1,b_2,…,b_{n+1}$ ，表示每名顾客的专属出价倍数。

$1 \le T \le 10$

对于每组数据： $1 \le n \le 2 \times 10^5,1 \le m \le 10^9,1 \le a_i \le 10^9,1 \le b_i \le 10^9$

对于每个测试用例，输出一个整数，表示所需进货货物的最小的价值 $v$ ，如果已经满足题意，输出 $0$ 即可。