Problem F. Вася и Суперкомпьютер

Author:Ю. Михалев   Time limit:1 sec
Input file:Standard input   Memory limit:256 Mb
Output file:Standard output  


Programmer Vasya decided to become a man, who solved most problems. To make his wish come true he invented a Supercomputer, which could do next tasks: generate a random problem (0) and solve a random problem (1) instead of Vasya (the problem may not be generated by the first task - Vasya already had an unlimited list of problems to solve).

Unfortunately, implementation features didn't allow to keep the Supercomputer on all day long: every day it could do limited number of tasks. Furthermore, every day the supercomputer must start with the task of the same type, which he ended previous day (first day could be started with any task).

So, Supercomputer worked several days and then broke down. In Supercomputer's log Vasya found that all records are shuffled and there are extra records, which don't belong to this log. You should help Vasya to count maximum count of completed tasks that Supercomputer could do before crash.

Input format

The first line of the input file contains one number N - number of records in the log

Following N lines contains number Mi - number of tasks, completed in some day, and a string Si of Mi characters 0 and 1 - description of tasks, completed in that day.

Log records are not chronologically ordered. Some records could be excess.

Output format

The output file must contain one number - maximum number of tasks, which Supercomputer could do before the crash.


Total length of all Si does not exceed 5 ⋅ 105

Sample tests

No. Standard input Standard output
4 1111
3 100
5 00101
2 00
10 1001010110
2 01
3 100
5 10100
2 11
6 011101
3 110
2 10

0.103s 0.013s 15