有效算法

题目描述

给出长度为 $n$ 的正整数序列 $\{a_n\}$ 和 $\{b_n\}$。对于每个 $a_i（1 ≤ i ≤ n）$，进行恰好一次以下操作：

• 将 $a_i$ 变成满足 $|a_i − x| ≤ k × b_i$ 的任意整数 $x$。

请你求出最小的非负整数 $k$，使得存在至少一种方法使得操作后序列 $\{a_n\}$ 所有数都相等。

输入格式

本题测试点包含多组数据。 第一行包含一个正整数 $T（1 ≤ T ≤ 1.5 × 10^5）$，表示数据组数。 对于每组数据： 第一行包含一个正整数 $n（2 ≤ n ≤ 3 × 10^5）$。 第二行包含 $n$ 个正整数 $a_1, a_2, . . . , a_n（1 ≤ a_i ≤ 10^9）$。 第三行包含 $n$ 个正整数 $b_1, b_2, . . . , b_n（1 ≤ b_i ≤ 10^9）$。 保证单个测试点中所有数据的 $∑n ≤ 3 × 10^5$。

输出格式

对于每组数据： 输出一行一个整数，表示答案。

样例 #1

样例输入 #1

2
4
8 3 3 5
1 2 3 2
5
4 3 4 5 6
3 1 3 1 1

样例输出 #1

2
2

提示

对于样例一，可以令 $a_i$ 全变为 $6$。 对于样例二，可以令 $a_i$ 全变为 $5$。