#CW26. 校准刻度(calibrate)

校准刻度(calibrate)

题目描述

小 Z 需要校准 nn 个测量装置。第 ii 个装置当前显示整数 viv_i,调节速率为正整数 sis_i。

小 Z 可以选择一个非负整数 kk。选定 kk 后,第 ii 个装置可以显示任意满足 ∣vi−zi∣≤ksi|v_i-z_i|\le ks_i 的整数 ziz_i。所有装置都要调节一次,并且调节后的读数必须相同。

请计算满足要求的最小非负整数 kk。

输入格式

第一行输入一个整数 TT,表示测试数据的组数。

对于每组数据:

  • 第一行输入一个整数 nn;
  • 第二行输入 nn 个整数 v1,v2,…,vnv_1,v_2,\dots,v_n;
  • 第三行输入 nn 个整数 s1,s2,…,sns_1,s_2,\dots,s_n。

输出格式

对于每组数据,输出一行一个整数,表示最小的 kk。

样例 1 输入

1
2
1 7
2 1

样例 1 输出

2

样例 1 解释

当 k=2k=2 时,两个装置可显示的整数范围分别为 [−3,5][-3,5] 和 [5,9][5,9],它们可以同时显示 55。当 k=1k=1 时,两个范围没有公共整数。

样例 2 输入

2
3
4 4 4
1 7 10
3
1 10 20
1 2 3

样例 2 输出

0
5

数据范围

对于所有测试数据,保证:

  • 1≤T≤1.5×1051 \le T \le 1.5\times 10^5;
  • 2≤n≤3×1052 \le n \le 3\times 10^5;
  • 1≤vi,si≤1091 \le v_i,s_i \le 10^9;
  • 单个测试点中,所有测试数据的 nn 之和不超过 3×1053\times 10^5。
数据类别 分值 测试点 附加条件
A 10 1∼21\sim 2 每组数据均满足 n≤20n \le 20
B 15 3∼53\sim 5 每组数据均满足 n≤2000n \le 2000
C 20 6∼96\sim 9 每组数据中的 viv_i 全部相同,或 sis_i 全部相同
D 25 10∼1410\sim 14 vi≤106v_i \le 10^6
E 30 15∼2015\sim 20 无额外限制