Floor Plan

Interview

Time limit1sMemory limit128 MB

Summary

Given a grid of walls and floor cells, count connected rooms, sort them by size, floor as many of the largest rooms as the wood supply allows, and report how many rooms got flooring plus the leftover wood.

Level: Medium4 of 10
Topics: DFS, Sorting, Implementation, Array
Solved: No attempts yet

Problem

The floor plan of a house is given on a grid. The character I is a wall and the character . is room floor space; each character occupies $1$ square metre. Doorways are not shown.

A room is a maximal group of . cells connected horizontally or vertically. No room is larger than $64$ square metres.

You are given a supply of hardwood flooring measured in square metres. You install the flooring starting with the largest room, then the next largest, and so on. Flooring a room consumes an amount of wood equal to its area, you may not skip any room, and you must stop as soon as you do not have enough wood for the next room.

Output how many rooms receive flooring and how many square metres of flooring are left over.

Input

Line 1: an integer, the number of square metres of flooring you have.
Line 2: an integer $r$ ( $1 \le r \le 25$ ), the number of rows in the grid.
Line 3: an integer $c$ ( $1 \le c \le 25$ ), the number of columns in the grid.
The next $r$ lines each contain $c$ characters of grid data (I or .).

Output

Print exactly one line in the format

K rooms, M square metre(s) left over

where $K$ is the number of rooms that received flooring and $M$ is the number of square metres left over.

Examples2

Example 1

Input

105
14
16
IIIIIIIIIIIIIIII
I......I.......I
I......III.....I
I........I.....I
I........IIIIIII
IIIIIIIIII.....I
I.I......I.....I
III..III.I.....I
I....I.IIIII...I
I....I.....III.I
I....I.......I.I
I....I.....III.I
I....I.....I...I
IIIIIIIIIIIIIIII

Expected output

4 rooms, 1 square metre(s) left over

Example 2

Input

13
2
3
.I.
.I.

Expected output

2 rooms, 9 square metre(s) left over