肆叶和小小靖参加了一场学校举办的公益黏土卫生二人组队比赛。 规则是二人获得 n个黏土盒，一个黏土盒中有一些有顺序的黏土块，每个黏土块都有脏值 p(1 ≤ p≤ 9)。 这些黏土块按顺序贴在一起形成了黏土的脏值。例如：黏土块为1,2,3,4，则黏土的脏值为 1234。 肆叶和小小靖得到黏土盒后会轮流处理所有黏土块：

• 肆叶：将所有黏土块揉成一个黏土团，其脏值为所有黏土块的脏值之和。
• 小小靖：将最终黏土团按位拆开，例如 1234 →1,2,3,4。 比赛要求将黏土脏值降到最小。 处理后的黏土团会留在盒中，其脏值会被科技净化，二人获得等量卫生值。 之后肆叶与小小靖按约定分配黏土盒：
• 肆叶选择 前 x 个黏土盒 获得卫生值
• 小小靖选择 后 x 个黏土盒 奖励一共有 n 种，肆叶对每一种奖励都有一个期望值，每个奖励兑换都需要一定卫生值。 肆叶希望获得的奖品的 期望总值 ≥k，想知道自己至少要选前多少个黏土盒才可以达到这个目标。

输入格式：

第一行一个数字 T 表示有T次询问 这T次询问中: 第一行:n k 表示有n个黏土盒和奖品，肆叶希望的总期望值为k 第二行:n个数字，第i个数字表示表示肆叶对第i个奖品的期望值 第三个:n个数字，第i个数字表示第i个奖品所需卫生值 第四行:n个数字，第i个数字是按顺序排列在一起的黏土块组成的黏土的藏值。比如1234就是四个黏土块(藏值分别为1,2,3,4)藏值排列在一起的黏土的藏值。

输出格式：

输出 T 行，每行一个答案：

• 若肆叶选前 x 个黏土盒即可满足要求，输出 x
• 若无法达成目标，输出 -1
  

输入样例 1：

10
5 7
3 5 6 1 5
2 4 2 3 6
4478 182319 279992 5799 86324
5 7
6 3 9 4 1
10 3 4 9 5
952715 228 155855 93334 919
7 47
3 5 5 8 8 9 3
9 6 10 1 3 3 6
588 582 4756 535 697727 61299 173988
7 20
9 2 3 8 2 4 6
1 10 2 7 6 10 4
7477 935 872466 7713 884782 933295 65352
3 6
5 3 10
2 6 8
775 514524 52717
5 8
7 5 8 9 4
7 5 3 1 5
31775 814213 44412 62171 52694
3 33
8 3 6
2 2 8
25959 893 629
6 48
1 4 10 8 4 7
9 8 2 8 1 9
754 622297 45685 468 61415 39851
4 21
10 7 8 2
10 4 2 8
485 6797 585397 279134
8 24
7 2 6 2 1 8 8 2
1 6 6 6 4 4 9 6
749 1196 745 224 298 648753 85736 116

输出样例 1：

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

数据范围：

• 黏土盒数量 n：1 ≤ n ≤ 5000
• 单个黏土脏值 d：1 ≤ d ≤ 10^200000
• 奖品所需卫生值 e：1 ≤ e ≤ 200000
• 期望目标 k：1 ≤ k ≤ 1e9
• T 次询问中所有 n 总和 ≤ 5000
• T 次中 ∑(黏土脏值长度) ≤ 10^200000