You are given two binary strings $a$ and $b$ of the same length. You can perform the following two operations on the string $a$:

  Swap any two bits at indices $i$ and $j$ respectively ($1 \le i, j \le n$), the cost of this operation is $|i - j|$, that is, the absolute difference between $i$ and $j$.  Select any arbitrary index $i$ ($1 \le i \le n$) and flip (change $0$ to $1$ or $1$ to $0$) the bit at this index. The cost of this operation is $1$. 

Find the minimum cost to make the string $a$ equal to $b$. It is not allowed to modify string $b$.


-----Input-----

The first line contains a single integer $n$ ($1 \le n \le 10^6$) — the length of the strings $a$ and $b$.

The second and third lines contain strings $a$ and $b$ respectively.

Both strings $a$ and $b$ have length $n$ and contain only '0' and '1'.


-----Output-----

Output the minimum cost to make the string $a$ equal to $b$.


-----Examples-----
Input
3
100
001

Output
2

Input
4
0101
0011

Output
1



-----Note-----

In the first example, one of the optimal solutions is to flip index $1$ and index $3$, the string $a$ changes in the following way: "100" $\to$ "000" $\to$ "001". The cost is $1 + 1 = 2$.

The other optimal solution is to swap bits and indices $1$ and $3$, the string $a$ changes then "100" $\to$ "001", the cost is also $|1 - 3| = 2$.

In the second example, the optimal solution is to swap bits at indices $2$ and $3$, the string $a$ changes as "0101" $\to$ "0011". The cost is $|2 - 3| = 1$.

Difficulty: competition

Starter code:

Solutions:
#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        print(*args, **kwargs, file=sys.stderr)
    dprint('debug mode')
except ModuleNotFoundError:
    def dprint(*args, **kwargs):
        pass



inId = 0
outId = 0
if inId>0:
    dprint('use input', inId)
    sys.stdin = open('input'+ str(inId) + '.txt', 'r') #标准输出重定向至文件
if outId>0:
    dprint('use output', outId)
    sys.stdout = open('stdout'+ str(outId) + '.txt', 'w') #标准输出重定向至文件
    atexit.register(lambda :sys.stdout.close())     #idle 中不会执行 atexit
    
N, = getIntList()

s1 = input() +'0'
s2 = input() +'0'

res = 0

i = 0
while i<N:
    if s1[i] != s2[i]:
        if s1[i+1] == s2[i] and s2[i+1] == s1[i]:
            res+=1
            i+=2
            continue
        res+=1
    i+=1
print(res)

    








n = int(input())
a = input()
b = input()

c = [10**10 for i in range(n + 10)]

c[0] = 0 if a[0] == b[0] else 1

for i in range(1, n):
    if a[i] == b[i]:
        c[i] = c[i - 1]
    elif a[i] == b[i - 1] and a[i - 1] == b[i]:
        c[i] = (1 + c[i - 2] if i > 1 else 1)
    c[i] = min(c[i], c[i - 1] + 1)
    
print(c[n - 1])


def read():
    return [c == '1' for c in input()]
n = int(input())
a, b = read(), read()

res = 0

i = 0
while i + 1 < n:
    if a[i] != b[i] and a[i] != a[i+1] and b[i] != b[i+1]:
        a[i] = b[i]
        a[i+1] = b[i+1]
        res += 1
        i += 2
    else:
        i += 1

for i in range(n):
    if a[i] != b[i]:
        res += 1

print(res)

n = int(input())
a = list(map(int, input()))
b = list(map(int, input()))

ans = sum(q != w for q, w in zip(a, b))
i = 1
while i < n:
    aii = a[i - 1]
    ai = a[i]
    bii = b[i - 1]
    bi = b[i]
    if aii + ai == 1 and bii + bi == 1 and aii != bii and ai != bi:
        ans -= 1
        i += 1
    i += 1

print(ans)


n = int(input())
a = list(input())
b = list(input())

count = 0
skip_next = False
for idx in range(n - 1):
    if skip_next:
        skip_next = False
        continue
    if a[idx] != b[idx] and a[idx] == b[idx + 1] and a[idx + 1] == b[idx]:
        count += 1
        a[idx] = b[idx]
        a[idx + 1] = b[idx + 1]
        skip_next = True

for idx in range(n):
    if a[idx] != b[idx]:
        count += 1
        # a[idx] = b[idx]

print(count)


n = int(input())
a = list(input())
b = list(input())

ans = 0
i = 0
while i < n:
    if a[i] != b[i]:
        ans += 1
        if i < n - 1 and a[i] == b[i + 1] and b[i] == a[i + 1]:
            i += 1
    i += 1
print(ans)


n  = int(input())

a  = list(map(int, input().strip()))
b  = list(map(int, input().strip()))

res = 0

for j in range(n-1):
    if (a[j]== 0) and (a[j+1 ] == 1 ) and (b[j] == 1) and (b[j+1 ] == 0):
        res +=1
        a[j ] = 1
        a[j+1] = 0
        
    elif  (a[j]== 1) and (a[j+1] ==0 ) and (b[j] == 0) and (b[j+1 ] == 1):
        res +=1
        a[j ] = 0
        a[j+ 1] = 1 

for j in range(n):
    if a[j] != b[j]:
        res += 1

print(res)

n = int(input())
a = str(input())
b = str(input())
k = True
result = 0
for i in range(n):
    if a[i] == b[i]:
        if k == False:
            result += 1
        k = True
    else:
        if k == False and z != a[i]:
            result += 1
            k = True
        elif k == False and z == a[i]:
            result += 1
        else:
            k = False
            z = a[i]
if k == False:
    result += 1
print(result)

n=int(input())
a=list(input())
b=list(input())
ans=0
for i in range(n-1):
    if a[i]!=b[i] and a[i]==b[i+1] and a[i+1]!=b[i+1] and a[i+1]==b[i]:
        ans+=1
        a[i],a[i+1]=a[i+1],a[i]
for i in range(n):
    if a[i]!=b[i]:
        ans+=1
print(ans)

def solve(a, b):
    i, n = 0, len(a)
    res = 0
    while i < n:
        if a[i] == b[i]:
            i += 1
            continue
        res += 1
        if i < n-1 and a[i+1] != b[i+1] and a[i] != a[i+1]: # exchange 01 => 10
            i += 2
        else:
            i += 1
    return res

input()
a = input().strip()
b = input().strip()
print(solve(a, b))

n=int(input())
a=input()
b=input()
c=False
f=0
l="12"
for i in range(n):
    if a[i]!=b[i]:
        if c:
            if l!=a[i]:
                c=False
                f+=1
            else:
                f+=1
        else:
            c=True
    else:
        if c:
            f+=1
        c=False
    l=a[i]
if c:
    f+=1
print(f)


n=int(input())
a=input()
b=input()
i=0
cost=0
while(i<n):
    if(a[i]==b[i]):
        i+=1
    
    elif(a[i]!=b[i] and i+1<n and a[i+1]!=b[i+1] and a[i]!=a[i+1]):
        i+=2
        cost+=1
    else:
        i+=1
        cost+=1
    
print(cost)

n = int(input())
a = input()
b = input()
count = 0
lst = []
index = 0
while index+1 < n:
    if a[index] != b[index]:
        count += 1
        if a[index] != a[index+1] and a[index] == b[index+1]:
            index += 1
    index += 1
if index < n and a[index] != b[index]:
    count += 1
print(count)


# import sys
# sys.stdin = open("F:\\Scripts\\input","r")
# sys.stdout = open("F:\\Scripts\\output","w")


MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))

n , = I()
s = input()
t = input()
ans = 0
i = 0
while i < n:
	if i < n-1 and (s[i]+s[i+1] == '01' and t[i]+t[i+1] == '10' or (s[i]+s[i+1] == '10' and t[i]+t[i+1] == '01')):
		ans += 1
		i += 2
	elif s[i] != t[i]:
		ans += 1
		i += 1
	else:
		i += 1
print(ans)


n = int(input())
a = input() + '$'
b = input() + '$'
weight = 0
i = 0
while i < n:
    if a[i] != b[i]:
        weight += 1
        if a[i] == b[i + 1] and a[i + 1] == b[i]:
            i += 2
            continue
    i += 1
print(weight)

n = int(input())
a = list(input())
b = list(input())
i = 0
num = 0
while i < n:
    if i == n - 1:
        if a[i] == b[i]:
            i += 1
        else:
            num += 1
            i += 1
    else:
        if a[i] == b[i]:
            i += 1
        elif a[i] == "1" and a[i + 1] == "0" and b[i] == "0" and b[i + 1] == "1":
            num += 1
            i += 2
        elif a[i] == "0" and a[i + 1] == "1" and b[i] == "1" and b[i + 1] == "0":
            num += 1
            i += 2
        elif a[i] != b[i]:
            num += 1
            i += 1

print(num)

N = int(input())
A = input()
B = input()
ans = 0
n = 0
while n < N:
	if A[n] != B[n]:
		ans += 1
		if n+1<N and A[n+1]==B[n] and B[n+1]==A[n]:
			n += 2
		else:
			n += 1
	else:
		n += 1
print(ans)


n=int(input())
a=[x for x in input()]
b=[x for x in input()]
ans=0
for i in range(n):
    if a[i] != b[i]:
        if i < n-1:
            if a[i] == b[i+1] and b[i] == a[i+1]:
                a[i]=b[i]
                a[i+1]=b[i+1]
                ans += 1
for i in range(n):
    if a[i] != b[i]:
        ans +=1
print(ans)

n=int(input())
s=list(input())
s1=input()
ans=0
for i in range(n):
    if s[i]!=s1[i]:
        if i!=n-1 and s[i]!=s[i+1] and s1[i+1]!=s1[i]:
            s[i]=s1[i]
            s[i+1]=s1[i+1]
        else:
            s[i]=s1[i]
        ans+=1
print(ans)
        


import atexit
import io
import sys
# import os

# from bisect import *
# from collections import *
# from fractions import gcd
# from fractions import Fraction as fr_
# from itertools import *
# import math

inf = float('inf')  # sys.maxint in py2
inf_neg = float('-inf')  # sys.maxsize = 9*1e18
range_5 = int(1e5 + 1)
range_6 = int(1e6 + 1)
range_7 = int(1e7 + 1)
range_8 = int(1e8 + 1)
# sys.setrecursionlimit(range_8)

_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER


@atexit.register
def write():
    sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())


def main():
    # n, k = map(int, input().split())
    n = int(input())
    a = list(input())
    b = list(input())
    ret = 0
    for i in range(n - 1):
        if(a[i] == '0' and b[i] == '1' and a[i + 1] == '1' and b[i + 1] == '0'):
            a[i], a[i + 1] = a[i + 1], a[i]
            ret += 1

        elif(a[i] == '1' and b[i] == '0' and a[i + 1] == '0' and b[i + 1] == '1'):
            a[i], a[i + 1] = a[i + 1], a[i]
            ret += 1

    for i in range(n):
        if (a[i] != b[i]):
            ret += 1

    print(ret)


def __starting_point():
    main()

__starting_point()

n = int(input())
str_a = input()
str_b = input()

a = []
b = []

for i in range(n):
    a.append(int(str_a[i]))
    b.append(int(str_b[i]))

res = 0
for i in range(n):
    if i < n - 1 and ((a[i] == 0 and a[i + 1] == 1 and b[i] == 1 and b[i + 1] == 0)or (a[i]) == 1 and a[i + 1] == 0 and b[i] == 0 and b[i + 1] == 1):
        a[i], a[i + 1] = b[i], b[i + 1]
        res+= 1
    else:
        if a[i] != b[i]:
            a[i] = b[i]
            res+= 1

print(res)

n = int(input())
a = list(input())
b = list(input())

cnt = 0

for i in range(n-1):
    if (a[i] == b[i+1]) and (a[i+1] == b[i]) and (a[i] != a[i+1]):
        cnt += 1
        a[i], a[i+1] = a[i+1], a[i]

for i in range(n):
    if a[i] != b[i]:
        cnt += 1

print(cnt)

n = int(input().strip())
a = input().strip()
b = input().strip()
a= [x for x in a]
b=[x for x in b]
sum = 0
li = []
dict = {}
for k in range(n):
    if (a[k] != b[k]):
        li.append(k)
        dict[k] = int(a[k])
if (len(li) == 0):
    print(0)
elif (len(li) == 1):
    print(1)
else:
    sum = 0
    int
    k = 0;
    while (k < len(li) - 1):
        if (dict[li[k]] != dict[li[k + 1]]):
            if (li[k + 1] - li[k] > 1):
                sum = sum + 1
                k = k + 1
            else:
                sum = sum + 1
                k = k + 2
        else:
            sum = sum + 1
            k = k + 1
    if(k==len(li)-1):
        sum=sum+1
    print(sum)


n=int(input())
a=input()
b=input()

ANS=0
i=0
while i<n:
    if a[i]==b[i]:
        i+=1
        continue

    if i+1<n and a[i+1]!=a[i] and a[i]==b[i+1]:
        ANS+=1
        i+=2
        continue

    else:
        ANS+=1
        i+=1

print(ANS)


import sys
input = sys.stdin.readline
n = int(input())
a = input()
b = input()
s = 0
i = 0
while i != len(a):
    if a[i] != b[i]:
        if a[i + 1] != b[i + 1] and a[i] != a[i + 1]:
            s += 1
            i += 2
        else:
            s += 1
            i += 1
    else:
        i += 1
print(s)