小X分砖块

题目描述:

小 X 喜欢跟着爸爸跑到建筑工地上去。 
这天，小 X看到一排砖，每块要么是白色的（0），要么是黑色的（1）。小 X 想把这排砖分成若干非空段，使得每段白砖和黑砖块数的比例相同。 
当然，小 X可以直接把整排砖作为一段，那就太简单了。为了增加难度，小 X 想知道最多能分成多少段，例如：100011 = 10 + 0011（即样例 1，最多分成 2 段，比例为 1:1）；0001110000000001 = 0001 + 11000000 + 0001（即样例 2，最多分成 3段，比例为 3:1） 。小 X 百思不得其解，希望你帮帮他。 

输入格式:

第一行包含一个整数 N。我们将用 N 行来描述这排砖，初始时这排砖为空。接下来 N 行，每行包含用一个空格隔开的两个整数 Ki,Ci（Ci 只可能是 0 或 1），表示在上一行描述完后尾部又有了 Ki 块颜色为 Ci 的砖。 

输出格式:

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

样例输入:

样例 1 
3 
1 1 
3 0 
2 1 

样例 2 
4 
3 0 
3 1 
9 0 
1 1 

样例输出:

样例 1 
2 

样例2
3

提示:

对于 30%的数据，N=1。 
对于 60%的数据，所有 Ki均相等。 
对于 100%的数据， 1≤N≤100000， 1≤Ki≤1000000000， 砖的总块数不超过 1000000000。 

时间限制: 1000ms
空间限制: 256MB

---