D. Размещение
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Энни — фотограф-любитель. Ей нравится фотографировать гигантские жилые дома ночью. Она только что сфотографировала огромное прямоугольное здание, которое можно представить как таблицу из $$$n \times m$$$ окон. Это означает, что в здании $$$n$$$ этажей и на каждом этаже ровно $$$m$$$ окон. Каждое окно либо тёмное, либо светлое, то есть в комнате за ним горит свет.

Энни знает, что каждая квартира в этом доме либо однокомнатная, либо двухкомнатная. Каждая однокомнатная квартира представлена на фотографии ровно одним окном, а каждая двухкомнатная квартира представлена на фотографии двумя подряд идущими окнами на одном этаже. Более того, $$$m$$$ гарантированно делится на $$$4$$$ и известно, что на каждом этаже ровно $$$\frac{m}{4}$$$ двухкомнатных квартир и ровно $$$\frac{m}{2}$$$ однокомнатных квартир. Точное расположение квартир неизвестно и может быть разным для каждого этажа.

Энни считает, что квартира заселена, если хотя бы в одном из её окон горит свет. Теперь она задаётся вопросом, какое может быть минимальное и максимальное количество заселённых квартир в доме, если судить по данной фотографии?

Формально, для каждого из этажей Энни придумывает возможное расположение квартир, в котором есть ровно $$$\frac{m}{4}$$$ двухкомнатных квартир (два последовательных окна) и $$$\frac{m}{2}$$$ однокомнатных квартир (одно окно). Затем она подсчитывает общее количество квартир, в которых есть хотя бы одно светлое окно. Какое минимальное и максимальное число она может получить?

Входные данные

Первая строка входных данных содержит два положительных целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \cdot m \leq 5 \cdot 10^5$$$) — количество этажей в здании и количество окон на этаже соответственно. Гарантируется, что $$$m$$$ делится на $$$4$$$.

Затем следует $$$n$$$ строк, каждая из которых содержит $$$m$$$ символов. $$$j$$$-й символ $$$i$$$-й строки равен «0», если $$$j$$$-е окно на $$$i$$$-м этаже тёмное, и равен «1», если это окно светлое.

Выходные данные

Выведите два целых числа, минимальное и максимальное возможное количество заселённых квартир, если на каждом этаже возможно своё собственное расположение $$$\frac{m}{4}$$$ двухкомнатных и $$$\frac{m}{2}$$$ однокомнатных квартир.

Примеры
Входные данные
5 4
0100
1100
0110
1010
1011
Выходные данные
7 10
Входные данные
1 8
01011100
Выходные данные
3 4
Примечание

В первом примере каждый этаж состоит из одной двухкомнатной квартиры и двух однокомнатных квартир.

При следующей планировке квартир достигается минимально возможное количество заселённых квартир, равное $$$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|