问题描述

考虑到安全指数是一个较大范围内的整数、小菜很可能搞不清楚自己是否真的安全，顿顿决定设置一个阈值 $\theta$，以便将安全指数 $y$ 转化为一个具体的预测结果——“会挂科”或“不会挂科”。

因为安全指数越高表明小菜同学挂科的可能性越低，所以当 $y\ge\theta$ 时，顿顿会预测小菜这学期很安全、不会挂科；反之若 $y<\theta$，顿顿就会劝诫小菜：“你期末要挂科了，勿谓言之不预也。”

顿顿准备从过往中寻找最佳阈值。具体来说，顿顿评估了 $m$ 位同学上学期的安全指数，其中第 $i$（$1\le i\le m$）位同学的安全指数为 $y_i$，是一个 $[0,10^8]$ 范围内的整数；同时，该同学上学期的挂科情况记作 $\text{result}_i\in\{0,1\}$，其中 $0$ 表示挂科、$1$ 表示未挂科。

相应地，顿顿用 $\text{predict}_\theta(y)$ 表示根据阈值 $\theta$ 将安全指数 $y$ 转化为的具体预测结果：

$$\text{predict}_\theta(y)= \begin{cases} 0 & (y<\theta)\\[4pt] 1 & (y\ge\theta) \end{cases} $$

若 $\text{predict}_\theta(y_j)$ 与 $\text{result}_j$ 相同，则说明阈值为 $\theta$ 时顿顿对第 $j$ 位同学是否挂科预测正确；不同则说明预测错误。

顿顿设计如下公式来计算最佳阈值 $\theta^\ast$：

$$\theta^\ast=\max\arg\max_{\theta\in\{y_i\}} \sum_{j=1}^m \bigl(\text{predict}_\theta(y_j)==\text{result}_j\bigr) $$

该公式等价于如下规则：

1. 最佳阈值仅在 $\{y_i\}$ 中选取（即与某位同学的安全指数相同）；
2. 按照该阈值对这 $m$ 位同学上学期的挂科情况进行预测，预测正确的次数最多（即准确率最高）；
3. 若多个阈值均可以达到最高准确率时，选取其中最大的。

请你根据给定的历史数据，求出最佳阈值 $\theta^\ast$。

输入格式

第一行包含一个正整数 $m$。

接下来 $m$ 行，每行包含两个用空格分隔的整数 $y_i$ 和 $\text{result}_i$（$0\le y_i\le 10^8$，$\text{result}_i\in\{0,1\}$），表示第 $i$ 位同学的安全指数和实际未挂科/挂科结果。

输出格式

输出一个整数，表示最佳阈值 $\theta^\ast$。

输入样例 1

6
0 0
1 0
1 1
3 1
5 1
7 1

输出样例 1

3

输入样例 2

8
5 1
5 0
5 0
2 1
3 0
4 0
100000000 1
1 0

输出样例 2

100000000

说明

样例 1 解释：

候选阈值为 $\{0,1,3,5,7\}$。

• $\theta=0$ 时，预测正确次数为 $4$；
• $\theta=1$ 时，预测正确次数为 $5$；
• $\theta=3$ 时，预测正确次数为 $5$；
• $\theta=5$ 时，预测正确次数为 $4$；
• $\theta=7$ 时，预测正确次数为 $3$。

阈值选取为 $1$ 或 $3$ 时准确率最高，为 $5$ 次；按规则三取最大的，故 $\theta^\ast=3$。

数据范围

• $70\%$ 的测试数据保证 $m\le 200$；
• 全部的测试数据保证 $2\le m\le 10^5$。