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

Автор:Ю. Михалев   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

Суммарная длина Si не превышает 5 ⋅ 105

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

Стандартный вход Стандартный выход
1
6
4 1111
3 100
5 00101
2 00
10 1001010110
2 01
26
2
6
3 100
5 10100
2 11
6 011101
3 110
2 10
16

0.349s 0.015s 13