Все мы понемногу воруем. Но у меня только одна рука, а у моих противников — две.
Álvaro Obregón, бывший президент Мексики
Альваро и Хосе — единственные кандидаты, претендующие на пост президента Тепито — прямоугольной сетки из \(2\) строк и \(n\) столбцов, где каждая клетка представляет собой дом. Гарантируется, что \(n\) кратно \(3\).
Согласно системе голосования Тепито, сетка будет разбита на округа, состоящие из любых \(3\) домов, которые связаны между собой\(^{\text{∗}}\). Каждый дом будет принадлежать ровно одному округу.
Каждый округ будет голосовать один раз. Округ будет голосовать за Альваро или Хосе соответственно, если их выберут не менее \(2\) домов в этом округе. Таким образом, всего будет подано \(\frac{2n}{3}\) голосов.
Поскольку Альваро является действующим президентом, он точно знает, какого кандидата выберет каждый дом. Определите максимальное количество голосов, которое Альваро может получить, если он оптимально распределит дома по округам.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальное количество округов, которое может выиграть Альваро, оптимально разделив дома на округа.