题目描述

从前有一根数轴， $0$ 时刻你在数轴上放置两个机器人，位置任意。

机器人可以左右移动，其最大速度是每秒 $k$ 单位。

给出 $n$ ，现在我们知道 $n$ 件事情：有一个金币将于时刻 $t_i$ 在位置 $x_i$ 出现。金币只会出现一瞬间：某个机器人 $t_i$ 时刻恰好在位置 $x_i$ 才能捕捉到该金币。

你可以规划机器人的放置及移动方式，目标是要捕捉所有金币。

请求出达到目标所需的最大速度 $k$ 的最小值。如果 $k$ 不是整数，请输出其向上取整的结果；如果不存在 $k$ 使得目标能够完成，请输出 $-1$ 。

输入格式

第一行包含一个整数 $n$ ，表示出现的金币数量。

接下来 $n$ 行，每行包含两个整数 $t_i,x_i$ ，表示该金币出现的时间和地点。

输出格式

输出一行一个整数，表示所需速度 $k$ 的最小值向上取整的结果，若无解则输出 $-1$ 。

样例

样例输入

5
1 1
3 7
3 4
4 3
5 10

样例输出

2

数据范围

对于所有数据，$1\le n\le 10^6$ ；对于 $1\le i<n$ ，$t_i\le t_{i+1}$ 。

保证不存在 $i,j$ 满足 $1\le i<j\le n$ 且 $t_i=t_j,c_i=c_j$ 。

子任务 1 ( 20% ) : $n\le 100$ 。

子任务 2 ( 20% ) : $n\le 1000$。

子任务 3 ( 30% ) : $n\le 10^5$ 。

子任务 3 ( 30% ) : 无特殊限制。