Bulbs

Time limit1sMemory limit128 MB

Summary

Given a target 2×N binary grid, find the minimum number of toggle operations on contiguous row or column segments to reach that pattern.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Matrix
Solved: No attempts yet

Problem

2×N bulbs are arranged in two rows. Each row has N bulbs, and initially every bulb is off.

Hyunsu wants to create a desired beautiful pattern in several operations. In one operation, he chooses one or more consecutive bulbs in a single row or a single column, then toggles all chosen bulbs. An off bulb becomes on, and an on bulb becomes off.

Given the target pattern, determine the minimum number of operations needed to create it.

Input

The first line contains the number of columns N. (1 ≤ N ≤ 10,000)

The next two lines describe the pattern Hyunsu wants to create. 1 means the bulb is on, and 0 means the bulb is off.

Output

Output the minimum number of operations needed to create the desired pattern.

Examples3

Example 1
Input
```
3
100
000
```
Expected output
```
1
```
Example 2
Input
```
5
11011
11011
```
Expected output
```
3
```

Example 3

Input

20
11101101111000101010
01111101100000010100

Expected output