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

Условие

Программист Вася решил войти в историю, как человек, решивший больше всего задач. Поэтому он создал Суперкомпьютер, способный выполнять следующие задания: генерировать случайную задачу(0) и решать случайную задачу(1) за Васю (задача необязательно должна быть перед этим сгенерирована - у Васи уже был безлимитный список задач для решения).

К сожалению, особенности реализации не позволяли Суперкомпьютеру работать постоянно: каждый день он мог выполнить только ограниченное количество заданий. Более того, каждый день суперкомпьютер должен был начинать работу с задания такого же типа, на котором он закончил вчера (первый день мог начаться с любого задания).

Так Суперкомпьютер проработал некоторое количество дней, а затем вышел из строя. Открыв лог, Вася обнаружил, что все записи о днях перемешались, и среди них оказались лишние. Помогите Васе выяснить, какое максимальное количество заданий мог выполнить Суперкомпьютер до поломки, исходя из данных лога.

Формат входных данных

Первая строка входного файла содержит число N - количество записей в логе

Следующие N строк содержат число M_i - количество заданий, выполненное в какой-то день, и строку S_i длины M_i, состоящую из символов 0 и 1 - описание выполненных в этот день заданий

Записи лога идут не по хронологическому порядку. Некоторые записи могут оказаться лишними.

Формат выходных данных

Выходной файл должен содержать единственное число - максимальное количество заданий, которое мог выполнить Суперкомпьютер до выхода из строя.

Ограничения

Суммарная длина S_i не превышает 5 ⋅ 10⁵

Примеры тестов

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