Решение задачи Обеспокоенные жильцы с Codeforces

На главной улице Берлятова стоит одноэтажный дом, в котором есть n квартир. Вова наблюдает за этим домом каждую ночь. Дом может быть представлен как массив, состоящий из n целых чисел a1,a2,…,an, где ai=1, если в i-й квартире включен свет, и ai=0 иначе.

Вова думает, что жильцы i-й квартиры обеспокоены и не могут спать тогда и только тогда, когда 1
Вова задался следующим вопросом: чему равно минимальное число k такое, что если жильцы ровно k попарно различных квартир выключат свет, то никто не будет обеспокоен? Ваша задача — найти это число k.