题目描述

在一条笔直的街道上，安装了一排编号为 $1,2,3,4,\dots$ 的路灯，每盏路灯只有开和关两种状态。初始时所有路灯都是关着的。

每按一次路灯的开关，它的状态就会翻转：原来开着的变成关着，原来关着的变成开着。

小华进行了若干次操作。每次操作给出两个参数：一个实数 $a$ 和一个正整数 $t$。这次操作会依次按下编号为 $\lfloor a\rfloor,\lfloor 2a\rfloor,\lfloor 3a\rfloor,\dots,\lfloor ta\rfloor$ 的路灯开关各一次。其中 $\lfloor k\rfloor$ 表示实数 $k$ 的整数部分（向下取整）。

所有操作完成后，恰好只有一盏路灯是亮着的。请计算这盏路灯的编号。

输入格式

第一行一个正整数 $n$，表示操作次数。

接下来 $n$ 行，每行两个数 $a_i$ 和 $t_i$，描述一次操作。其中 $a_i$ 是实数（小数点后恰好有 $6$ 位），$t_i$ 是正整数。

输出格式

仅一行一个正整数，表示亮着的那盏路灯的编号。

样例

3
1.618034 13
2.618034 7
1.000000 21

20

提示

记 $T=\sum \limits_{i=1}^n t_i$。

• 对于 $30\%$ 的数据，$T \le 1000$；
• 对于 $80\%$ 的数据，$T \le 200000$；
• 对于 $100\%$ 的数据，$T \le 2000000$；
• 对于 $100\%$ 的数据，$n \le 5000$，$1 \le a_i \lt 1000$，$1 \le t_i \le T$。

数据保证最终恰好只有一盏路灯是亮着的，无需判断错误情况。且对所有 $i$，$t_i \times a_i$ 的最大值不超过 $2000000$。