Энни — фотограф-любитель. Ей нравится фотографировать гигантские жилые дома ночью. Она только что сфотографировала огромное прямоугольное здание, которое можно представить как таблицу из \(n \times m\) окон. Это означает, что в здании \(n\) этажей и на каждом этаже ровно \(m\) окон. Каждое окно либо тёмное, либо светлое, то есть в комнате за ним горит свет.
Энни знает, что каждая квартира в этом доме либо однокомнатная, либо двухкомнатная. Каждая однокомнатная квартира представлена на фотографии ровно одним окном, а каждая двухкомнатная квартира представлена на фотографии двумя подряд идущими окнами на одном этаже. Более того, \(m\) гарантированно делится на \(4\) и известно, что на каждом этаже ровно \(\frac{m}{4}\) двухкомнатных квартир и ровно \(\frac{m}{2}\) однокомнатных квартир. Точное расположение квартир неизвестно и может быть разным для каждого этажа.
Энни считает, что квартира заселена, если хотя бы в одном из её окон горит свет. Теперь она задаётся вопросом, какое может быть минимальное и максимальное количество заселённых квартир в доме, если судить по данной фотографии?
Формально, для каждого из этажей Энни придумывает возможное расположение квартир, в котором есть ровно \(\frac{m}{4}\) двухкомнатных квартир (два последовательных окна) и \(\frac{m}{2}\) однокомнатных квартир (одно окно). Затем она подсчитывает общее количество квартир, в которых есть хотя бы одно светлое окно. Какое минимальное и максимальное число она может получить?
Выходные данные
Выведите два целых числа, минимальное и максимальное возможное количество заселённых квартир, если на каждом этаже возможно своё собственное расположение \(\frac{m}{4}\) двухкомнатных и \(\frac{m}{2}\) однокомнатных квартир.
Примечание
В первом примере каждый этаж состоит из одной двухкомнатной квартиры и двух однокомнатных квартир.
При следующей планировке квартир достигается минимально возможное количество заселённых квартир, равное \(7\).
|0 1|0|0|
|1 1|0|0|
|0|1 1|0|
|1|0 1|0|
|1|0|1 1|
При следующей планировке квартир достигается максимально возможное количество заселённых квартир, равное \(10\).
|0 1|0|0|
|1|1 0|0|
|0 1|1|0|
|1|0 1|0|
|1 0|1|1|
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 4
0100
1100
0110
1010
1011
|
7 10
|
|
2
|
1 8
01011100
|
3 4
|