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.
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.
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