Aircraft carrier Admiral Kuznetsov's deck can hold up to ~N~ aircraft in line. Today's challenge will be to reach a certain aircraft configuration in the shortest time possible.
All aircraft are on deck with their crews. In one unit of time, one of three things can happen:
Four aircraft in consecutive spots simultaneously take off in formation.
Three aircraft in consecutive spots simultaneously take off in formation.
One aircraft lands at an empty spot on deck.
There is an infinite number of land-based aircraft in the air, so the third operation can always be called.
Subtask 1 [20%]
~3 \le N \le 14~
Subtask 2 [80%]
~3 \le N \le 10^6~
(new cases for ~N = 5~ in addition to contest data)
The first line contains integer ~N~.
The next line contains a string of length ~N~, with ~1~ representing an aircraft present and ~0~ representing an empty spot on the deck.
The next line contains a string of length ~N~, with ~1~ representing an aircraft and ~0~ representing an empty spot in the final configuration.
Output the minimum units of time required to reach the final configuration.
If the final configuration can not be reached, print
7 1100111 0000000
One aircraft lands at position ~3~.
Aircrafts ~1-3~ take off.
Aircrafts ~5-7~ take off.