← 返回题目列表

Codeforces · 1804/D

D. 住宿

中文机器翻译题面 查看原题

安妮是一位业余摄影师。她喜欢在夜间拍摄巨型住宅楼的照片。她刚刚拍了一张巨大的矩形建筑的照片,它可以看作是一张由 $$$n \times m$$$ 窗户组成的桌子。这意味着该建筑物有 $$$n$$$ 层,每层恰好有 $$$m$$$ 窗户。每扇窗户要么是暗的,要么是亮的,这意味着窗户后面的房间里有灯打开。

Annies 知道这栋楼的每间公寓要么是一居室,要么是两居室。每间一卧室公寓都只有一个窗户代表其在图片上的位置,而每间两卧室公寓在同一层楼上正好有两个连续的窗户。此外,$$$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$$$ 个字符。如果 $$$i$$$ 第 $$$i$$$ 层上的第 $$$j$$$ 窗口是暗的,则第 $$$i$$$ 行的第 $$$j$$$ 字符为“0”,如果该窗口是亮的,则该字符为“1”。

输出

打印两个整数,即占用的公寓的最小可能数量和占用的最大公寓数量,假设每个楼层都可以有 $$$\frac{m}{4}$$$ 两居室公寓和 $$$\frac{m}{2}$$$ 一居室公寓的单独布局。

示例

输入 #1

5 4
0100
1100
0110
1010
1011

输出 #1

7 10

输入 #2

1 8
01011100

输出 #2

3 4

注意

在第一个示例中,每层由一间两卧室公寓和两间一卧室公寓组成。

以下公寓布局实现了占用公寓的最小可能数量等于 $$$7$$$。

以下公寓布局可实现最大可能的入住公寓数量等于 $$$10$$$。