题目描述

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

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

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

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

输入格式

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

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

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

输出格式

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

样例数据

input

3

1 1

3 0

2 1

output

2

数据规模与约定

时间限制：$1 \text{s}$

空间限制：$128 \text{MB}$