题目描述

Bessie有一个两行N列的矩形，每个格子要么是白色（用字符‘.’表示），要么是黑色（用字符‘#’表示）。下面定义“白色路径”，“白色路径”是由若干个白色格子构成，该路径上相邻的两个白色格子必须有公共边，而且“白色路径”的第一个格子一定是矩形第一列的格子，“白色路径”的最后一个格子一定是矩形最后一列的格子。输入数据保证，至少有一条满足题意的“白色路径”。Bessie比较喜欢黑色格子，所以Bessie想把尽可能多的白色格子染成黑色格子，但是前提是必须保证染色后，至少还存在一条“白色路径”。

输入格式

第一行，一个整数N。表示矩形是两行N列的。

接下来是有两行，每行有N个字符，字符‘.’表示白色格子，字符‘#’表示黑色格子。

输出格式

一个整数，Bessie最多可以把多少个白色格子染成黑色格子？前提是必须保证染色后至少还存在一条“白色路径”。

样例输入/输出

5
#....
...#.

2

样例解释

#. . . .

. . ###

数据规模与提示

1、对于40%的数据，N <= 5。

2、对于70%的数据，N <= 10。

3、对于100%的数据，N <= 50。