题目描述

农民约翰的${N}$头牛（${1<=N<=100000}$）站在沿途的不同位置一维长栅栏。

第${i}$头奶牛站在位置${x_i}$（范围为${0...}$${1000000000}$的整数）并且已经繁殖了(${b_i}$对于格恩西岛或"${H}$"代表荷斯坦）。

没有两头奶牛占据同一位置。

${FJ}$要为县城拍连续间隔的奶牛照片 公平，但我们希望他的所有品种都能在照片中得到公平的体现。

因此，他希望确保，对于存在于 照片，每个品种的数量相同（例如，一张带有 所有荷斯坦牛都可以，与 ${27 }$只荷斯坦牛和 ${27 }$根西岛的合影还可以，但是 与 ${10 }$只荷斯坦和 ${9 }$只根西岛合影不合适）。

帮助${FJ}$参加他的公平 通过找到满足 ${FJ }$的 照片的最大尺寸来拍摄照片 约束。

照片的大小最大和最大之间的差异 照片中奶牛的最小位置。

${FJ}$有可能 最终只拍了一头牛的照片，在这种情况下，这张照片会 大小为零。

输入格式

第${1}$行：整数${N.}$

第${2...}$${1+N}$行：${i+1}$行包含${x_i}$和${b_i}$。

输出格式

第${1}$行：一个整数，表示展会的最大规模照片

样例

输入样例

6
4 G
10 H
7 G
16 G
1 G
3 H

输出样例

7

提示

输入详细信息： 有六头奶牛的品种（从左到右）为${G}$、${H}$、${G}$、${G}$、${H}$、${G}$。

样本输出 ${7}$个输出细节：农民约翰能拍到的最大的${fair photo}$是中间${4}$头奶牛，其中包括${2}$头霍尔斯泰牛和${2}$头根西岛牛。