5729 - 砖块

小林有一排砖,每块要么是白色的(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为同一个数。

输出

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

样例

输入

3
1 1
3 0
2 1

输出

2

输入

4
3 0
3 1
9 0
1 1

输出

3

提示

【数据规模】

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

对于60%的数据满足:所有的ki均相等。

对于100%的数据满足:1≤N≤105,1≤k_i10^9,砖的总块数不超过109。

来源

课课通

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题