Separate the psychopaths! Dr. Trump is the head psychiatrist at a mental hospital, which is populated by murdering psychopaths. If 2 psychopaths are left together, they will end up brutally injuring or even killing each other, so Dr. Trump needs to build walls to separate these psychopaths, but owing to the limited amount of funds he has left, he has to minimise the number of walls he builds. Walls of a room can either be horizontal or vertical in nature and of any length.

Help Dr. Trump minimise the number of walls he builds to separate all the psychopaths in a 2*n psych ward.

Also, do keep in mind that the shortest code wins.

Input

The first 2 lines contains the position of psychopaths (denoted by '#') and empty spaces (denoted by '-').

Output

An integer which is equal to the minimum number of walls to build to separate all the psychopaths from each other.

Input Constraints

1 &lt;= n &lt;= 1000000

Sample Test Cases

Test Case 1

Sample Input

##########
##########


Sample Output

10


Test Case 2

Sample Input

#-#-#
-#-#-


Sample Output

3


Test Case 3

Sample Input

#-----
------


Sample Output

0
Python, 270 228 166 156 bytes

a=input();b=input();m=lambda s:[c=="#"for c in s];f=m(a);g=m(b);s=p=0
for i in range(len(a)):q=2*f[i]+g[i];r=p&amp;q;s+=r!=0;p=r or p|q
print(s+(any(f)&amp;any(g)))


PEP8-ified:

a = input()
b = input()
m = lambda s: [c == "#"for c in s]
f = m(a)
g = m(b)
s = p = 0
for i in range(len(a)):
    q = 2*f[i]+g[i]
    r = p &amp; q
    s += r != 0
    p = r or p | q
print(s+(any(f) &amp; any(g)))


Try it online!

This is my first time here, be gentle please ;)

There is always a horizontal wall in the middle, except when prisoners are only on one side -- the addition in print() takes this into account. Strategy here is to break horizontal bar into sections such that there is no more than one prisoner on each side, for each section.

The for loop uses an int, p, to hold two bit flags, indicating whether the current top/bottom section already contains a psychopath. We &amp; this with the flags from the new gridsquare to check whether we are going to overflow, and need to place a wall; if so, we increment s. We also use p&amp;q to decide how to update the state: if we overflow, we hold onto just the overflowed prisoner (p&amp;q). Otherwise, we | the new prisoners onto our current prisoner state. Using and and or as a ternary operator again here.

There are some helper functions at the top, as well as throwaway variable names for values used more than once.

Edit:
It seems like this got simpler as it got shorter. It used to use all kinds of wacky behaviour