该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

冬天了，太冷了！

徐老师听说冬天应该吃牛肉或者羊肉，可以御寒，于是充分发挥民主集中制，让广大学生投票选。

随着计票的进行，屏幕上会实时显示当前支持牛肉和羊肉的人数比例，徐校长一边刷手机，一边看屏幕，已知徐校长看了 $N$ 次屏幕，第 $i$ 次屏幕上显示的是 $a_i$ 和 $b_i$ ，问至少有多少人参加了投票。

每个人只能牛肉羊肉二选一，不能多选或者不选。

Format

Input

第一行一个正整数 $N$ 。

后面 $N$ 行，第 $i$ 行以既约形式给出徐校长第 $i$ 次看屏幕时支持牛肉和羊肉的人数比例。

所有输入都是不超过 1000 的正整数，且保证答案不超过 $10^{18}$ 。

Output

在一行中输出投票的最少人数。

Samples

3
1 1
4 5
1 4

20

Limitation

1s, 1024KiB for each test case.