题目描述

最喜欢的课是什么课？当然是：下！课！

梦云是量子千层披萨大学(Quantum Layered University of Pizza)的一名学生，下课后他决定预约第一智能餐厅的披萨。

披萨店中有 $n$ 瓶魔法调料和 $n$ 块魔法披萨，每瓶调料的价值为 $a_i$, 准备时间为 $b_i$，每块披萨有一个灵力值 $c_i$ 和 制作时间 $d_i$。梦云会提前打电话预约，此时所有的调料开始准备，所有的披萨开始制作。

每瓶魔法调料 $j$ 可以为任何编号小于 $j$ 的披萨 $i$ 增加 $​c_i \times a_j$ 的灵力。

梦云希望买到一块灵力至少为 $k$ 的披萨，由于要饿晕了，所以他希望你计算出他预约后最快多久，可以得到这样的一块披萨。如果无论等多久都不能买到灵力至少为 $k$ 的披萨，他就会感到被生活压扁，并愤怒地吃掉披萨店，此时你应该输出 $-1$。

形式化来说，你需要找到找到一个最小的 $t$，使得存在一个下标 $i (d_i \leq t)$，有

其中：

如果不存在这样的 $t$，输出 $-1$。

输入格式

本题为多测，第一行输入一个整数 $T (1 \leq T \leq 10^5)$，代表测试组数。

对于每组测试：

第一行输入两个整数 $n \enspace k (1 \leq n \leq 10^5, 1 \leq k \leq 10^{9})$。

第二行输入每瓶调料的价值 $a_i (1 \leq a_i \leq 10^5)$。

第三行输入每瓶调料的准备时间 $b_i (1 \leq b_i \leq 10^9)$。

第四行输入每块披萨的灵力值 $c_i(1 \leq c_i \leq 10^5)$。

第五行输入每块披萨的制作时间 $d_i(1 \leq d_i \leq 10^9)$。

保证所有测试组数中 $n$ 之和不超过 $10^5$。

输出格式

对于每组测试，输出一行整数 $t$，代表答案。特别地，如果没有 $t$ 满足要求，输出 $-1$。

样例

3
3 5
1 4 3
7 8 9
4 5 6
1 2 3
4 10
2 3 1 5
2 4 2 4
2 4 6 8
3 5 7 9
5 1919810
1 1 4 5 1
4 9 9 8 2
4 4 3 5 3
1 1 4 5 1

2
4
-1

样例解释

对于第一组数据，在等待时间为 $2$ 的时候就可以获得灵力值为 $5$ 的披萨。

对于第二组数据，在等待时间为 $4$ 的时候，可以将第 $2, 3, 4$ 瓶调料加入第 $1$ 块披萨，此时这块披萨的灵力值为 $2 + 2 \times (3+1+5) = 20$，大于等于 $k$。

对于第三组数据，梦云最多获得灵力值为 $48$ 的披萨，因此他会愤怒地吃掉披萨店，输出 $-1$。