题目描述

给定长度为$n$的正整数序列$\{a_n\}$和$\{b_n\}$。对于每个$a_i$，需恰好进行一次操作：将$a_i$变为满足$|a_i - x| ≤ k×b_i$的任意整数$x$。求最小的非负整数$k$，使得操作后所有$a_i$相等。

输入格式

• 第一行：正整数$n$（$2 \le n \le 3×10^5$）。
• 第二行：$n$个正整数$a_1, a_2, ..., a_n$（$1 \le a_i \le 10^9$）。
• 第三行：$n$个正整数$b_1, b_2, ..., b_n$（$1 \le b_i \le 10^9$）。

输出格式

一个整数，表示最小的$k$。

样例

输入：

4
8 3 3 5
1 2 3 2

输出：

2

样例2

输入：

5
4 3 4 5 6
3 1 3 1 1 

输出：

2  

样例提示

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

数据分布

$40\%$ 的样例， $ 1\le n \le 100 , 1\le a_i \le 100, 1 \le b_i \le 100$

$100\%$ 的样例， $ 1\le n \le 3*10^5 , 1\le a_i \le 10^9, 1 \le b_i \le 10^9$