Kill the Monsters

In order to celebrate the 8th anniversary of ZOJ, watashi introduces a strange game to other ZJU ACM team members. The board of the game consists of 20X20 grids.

There're some monsters in the grid and 40 buttons along the board. Each row and column is controlled by a single button, while each button can be pushed ONLY ONCE.

If you push a row-controlling button, the health point of all the monsters in the corresponding row will decrease 1.
If you push a column-controlling button, the health point of all the monsters in the corresponding column will decrease 1.
The health point of each monster is 2 initially, and if the monster's health point is 0, we say that the monster has been killed. The goal of the game is to kill as many monsters as possible and you cannot push more than N buttons.

Though Watashi plays the game day and night, he cannot always achieve the perfect goal. Please help him to find the best solution of some specific boards.

Input

The first line of each test case contains the numbers N ( 1 <= N <= 40 ).

Then there're 20 lines, each with 20 characters. The jth character in the ith line correspond to the state in grid (i, j). '.' for the empty grid, '#' for a monster.

The input will contain no more than 10 test cases.

The last test case is followed by one zero.

Output

For each test case output one number, the maximum number of dead monsters.

Sample Input

3
....................
....................
..###...............
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
....................
10
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
0
Sample Output

2
25

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问