题目背景

波奇酱在梦中幻想自己正统领着军队与怪兽对战...

题目描述

对战从时刻 $1$ 初开始，波奇酱的军队由 $n$ 名士兵构成，若在某一时刻初选择让第 $i$ 名士兵发起攻击，那么第 $i$ 名士兵会在该时刻末对怪兽发起攻击会造成 $a_i$ 点伤害。怪兽的血量为 $x$ ，当怪兽的血量小于等于 $0$ 时，若当前处于时刻 $T$ 末，则称波奇酱在第 $T$ 时刻获胜。在某一时刻初，波奇酱可以指挥任意数量的不同士兵向怪兽发起攻击。不幸的是，每位士兵都存在攻击间隔 $c_i$ ，即当时刻 $T$ 末时第 $i$ 位士兵向怪兽发起攻击后，该士兵至少得等到时刻 $T+c_i$ 末才能再次发起攻击，并且一位士兵最多能攻击 $d_i$ 次怪兽。波奇酱想知道，自己至少在哪个时刻获胜。

输入格式

第一行包含一个整数 $t(1 \leq t \leq 2 \times 10^5)$ ，表示数据组数。

每组测试数据描述如下。

第一行包含两个整数 $ n,x (1 \leq n \leq 2 \times 10^5 , 1 \leq x \leq 10^9)$ ，表示波奇酱共有 $n$ 个士兵以及怪兽的血量为 $x$。

第二行包含 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个士兵向怪兽发动一次攻击可以造成 $a_i(1 \leq a_i \leq 10^9)$ 点伤害。

第三行包含 $n$ 个整数，第 $i$ 个整数 $c_i(1 \leq c_i \leq 2 \times 10^5)$ 表示第 $i$ 个士兵的攻击间隔。

第四行包含 $n$ 个整数，第 $i$ 个整数 $d_i (0 \leq d_i \leq 10^9)$ 表示第 $i$ 个士兵的最多攻击次数。

保证对于一个测试点的所有 $n$ 的总和不超过 $2 \times 10^5$ 。

输出格式

对于每组测试数据，输出一个整数，表示波奇酱获胜需要的最少时刻。若波奇酱无法战胜怪兽，请输出 $-1$。

输入输出样例 #1

2
3 12
4 4 4
1 2 3
1 1 1
3 12
4 4 4
1 2 3
1 1 0

1
-1

输入输出样例 #2

1
1 3
1
2
10000000

5

说明/提示

对于样例一的第一组测试用例，波奇酱只需要在时刻 $1$ 初时命令所有士兵对怪兽发起攻击，在时刻 $1$ 末时，怪兽的血量减为 $0$ ，按照规则，波奇酱于时刻 $1$ 获胜。

对于样例一的第二组测试用例，可以证明，波奇酱永远无法获胜。

对于样例二的第一组测试用例，波奇酱先在时刻1初时命令仅有的一名士兵对怪兽发起攻击，在时刻 $1$ 末时该士兵对怪兽造成 $1$ 点伤害，此时怪兽的血量从原来的 $3$ 减为 $2$ ；由于士兵的攻击间隔为 $2$ ，该士兵至少得等到时刻 $3$ 末才能再次发动攻击，波奇酱可以在时刻 $3$ 初命令该士兵向怪兽发起攻击，并在时刻 $3$ 末时对怪兽造成 $1$ 点伤害，怪兽的血量减为 $1$ ；同理，最终波奇酱可以在时刻 $5$ 末将怪兽的血量减为 $0$ ，由题意可知，波奇酱至少在时刻 $5$ 获胜。