Background

Special for beginners, ^_^

Description

小明有很多硬币，把储蓄罐占满了，所以他想把小面额的硬币兑换成更大面额的。

每次小明可以选择两枚相同面额的硬币兑换成一枚更大面额的硬币。

问在最优的兑换情况下（不允许借钱），剩下多少枚硬币。

Format

Input

第一行一个正整数 $N（\le10^5）$，表示有 $N$种不同面额的硬币。

接下来 $N$ 行每行两个数，$s_i（\le10^9）$，$c_i（\le10^9）$，表示有 $c_i$ 枚面值为 $s_i$ 的硬币。

Output

在一行中输出答案。

Samples

3
3 3
4 1
6 1

3

Limitation

1s, 1024KiB for each test case.