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

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

【数据规模】

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

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

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

课课通