题目描述

小X喜欢跟着爸爸跑到建筑工地上去。

这天，小X看到一排砖，每块要么是白色的 0，要么是黑色的 1 。小X想把这排砖分成若干非空段，使得每段白砖和黑砖块数的比例相同。

当然，小X可以直接把整排砖作为一段，那就太简单了。为了增加难度，小X想知道最多能分成多少段，例如：

• $100011=10+0011$
• $0001110000000001=0001+11000000+0001$

小X百思不得其解，希望你帮帮他。

输入格式

第一行包含一个整数 $N$。我们将用 $N$ 行来描述这排砖，初始时这排砖为空。

接下来 $N$ 行，每行包含用一个空格隔开的两个整数 $K_i,C_i$，表示在上一行描述完后尾部又有了 $K_i$ 块颜色为 $C_i$ 的砖。

输出格式

第一行包含一个整数，表示最多能分成的段数。

3
1 1
3 0
2 1

2

4
3 0
3 1
9 0
1 1

3

数据范围

对于 $30\%$ 的数据，$N=1$。

对于 $60\%$ 的数据，所有 $K_i$ 均相等。

对于 $100\%$ 的数据，$1 \le N \le 10^5，1 \le K_i \le 10^9$， $1 \le \sum K_i \le 10^9$。