Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
meteo
Каникулы надо тщательно планировать. В том числе и в зависимости от погоды. Если ожидается слошные "Мороз и солнце, день чудесный" - стоит пожить на даче, на лыжах покататься, рыбку половить. Если "Буря мглою небо кроет" все каникулы - готовимся сидеть дома, пить чай с печеньками и... нет, не фильмы смотреть, а решать задачки по прораммированию.
Каникулы длятся D дней. Имеются прогнозы на эти дни от N метеорологов. Но метеорологи - народ ненадёжный, им свойственно ошибаться. Но при этом про каждого метеоролога известно максимальное возможное количество ошибок в его прогнозе.
Разработайте программу, которая на основе этих данных определяет максимальное возможное количество сонечных дней в каникулы или приходит к выводу, что данные противоречивы (тогда прорамма должна вывести -1).
Входные данные. В первой строке натуральные числа D (длительность каникул)и N (количество метеорологов), оба числа не меньше 2 и не больше 15.
Далее следуют N строк с прогнозами и оценкой их точности. Прогноз - строка из D символов 0 или 1, 1 означает солнечный день, 0 - пасмурный. Далее после пробела в строке размещается целое неотрицательное число, максимальное возможное количество ошибок в этом прогнозе.
Выходные данные. Единственное целое число – максимальное возможное количество солнечных дней в каникулы или -1, в случае, если данные противоречивы.
Пример. При вводе значений
4 3
1100 2
0110 1
1110 3
программа должна вывести значение 3: таое количество солнечных дней
возможно, еслb первые 3 дня будут солнечными (первый и второй метеорологи совершили по одной ошибке - но это допутимо). А вот если ввести
4 3
1100 1
0110 1
0011 1
програма выведет -1, поскольку кто-то из метеорологов явно ошибся больше одного раза.
Для отправки решений необходимо выполнить вход.
|