0363. Компьютеры для сборов

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

Организаторы сборов собрали информацию о том, какие компоненты в каких компьютерах исправны, а какие – нет. Помогите им подсчитать, сколько рабочих компьютеров они могут получить.

Формат входного файла

Первая строка входного файла содержит два целых числа N и K – количество компьютеров, найденных организаторами и количество компонент в каждом из компьютеров (1 ≤ N ≤ 1000, 1 ≤ K ≤ 10). Далее следует N строк по K чисел в каждой. Каждая строка описывает один компьютер и содержит K чисел 0 или 1, которые описывают состояние соответствующих компонент компьютера: единица соответствует рабочему компоненту, ноль – неисправному.

Формат выходного файла

Выведите единственное число – максимальное количество рабочих компьютеров, которое смогут собрать организаторы сборов.

Пример:

Источник: Открытый зимний чемпионат ПетрГУ по программированию, 15 декабря 2013

Обсудить       Отправить решение



Версия для печати