Description

小林有一排砖，每块要么是白色的（0），要么是黑色的（1）。他想把这排砖分成若干非空段，使得每段白砖和黑砖块数的比例相同。

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

100011=10+0011（即样例1，最多分成2段，比例为1:1）；

0001110000000001=0001+11000000+0001（即样例2，最多分成3段，比例为3:1）。

Input Format

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

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

注意：可能有连续行的 $C_i$ 为同一个数。

Output Format

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

3
1 1
3 0
2 1

2

4
3 0
3 1
9 0
1 1

3

Hint

对于30%的数据满足：$N=1$。

对于60%的数据满足：所有的 $k_i$ 均相等。

对于100%的数据满足：$1≤N≤105，1 ≤k_i≤10^9，砖的总块数不超过$10^9$。