题目描述

为了庆祝自己的生日，小张推出一款游戏。游戏在一个 $20*20$ 的方格上进行，上面有一些怪物，用 "#" 表示，其他是空格，用 "." 表示。怪物有两点体力。体力为 $0$ 时死亡。

你可以进行以下操作：

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

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

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

输入格式

第一行为整数 $n$ ( $1 \le n \le 40$ ) ，表示操作的次数。

接下来是一个 $20*20$ 的方格，"#" 表示怪物，"." 表示空格。

格式参考输入样例。

输出格式

一个整数，代表最多能杀死的怪物数量。

样例

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

2

10
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################
####################

25