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

Statement

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 M_i - number of tasks, completed in some day, and a string S_i of M_i 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.

Constraints

Total length of all S_i does not exceed 5 ⋅ 10⁵

Sample tests

6
4 1111
3 100
5 00101
2 00
10 1001010110
2 01

26

6
3 100
5 10100
2 11
6 011101
3 110
2 10

16