问题描述

为了庆祝自己的生日, 乐乐推出了一款游戏. 游戏在一个 20*20 的方格上进行, 上面有一些怪物, 用 “#” 表示, 其他是空格, 用 “.” 表示. 怪物有两点体力, 体力为 0 时死亡. 你可以进行一下操作:

1. 使一个横行上的怪物体力减一.
2. 使一个竖行上的怪物体力减一.

对每个横行或竖行只能操作一次, 限定 n 次, 问最多能杀死多少个怪物.

输入格式

第一行一个整数 n (1 <= n <= 40), 表示操作的次数. 接着有一个 20*20 的方格, 用 “#” 表示怪物, 用 “.” 表示空格.

输出格式

输出最多能杀死的怪物数量.

样例

3
....................
....................
..###...............
...#.#..............
...#.#..............
....................
....................
....................
....................
....................
...........#........
....................
....................
....................
....................
....................
....................
....................
....................
....................

2