The Russian National Operating System (RNOS) is going to be released soon, and its help system is finished already. A user can open the front page of the help system by pressing the F1 button. If the front page is open, then pressing F1 will close it. This seems to be very simple, but the developers of the help system have applied some innovations…
The help information is presented on several pages, and each following page describes the same issues as the preceding page but in more detail and in a smaller type. Each page except for the last one has two buttons: “Open next page” and “Close next page.” Of all the open pages, the user can see only the least detailed one, while all the other pages are inaccessible.
You want to learn using the help of the RNOS. Start with the simple task of changing the set of open help pages in a minimum number of operations.
The first line contains the number n of help pages in the RNOS (1 ≤ n ≤ 50). In the second line you are given the initial set of open pages in the form of a line consisting of n ones and zeros. The i-th symbol is 1 if the i-th page is open and 0 otherwise. In the third line you are given the required set of open pages in the same format.
Output the minimum number of operations (mouse clicks and keystrokes) necessary for changing the set of open pages.
The optimal sequence of operations: close the first page by pressing F1, close the third page using the button on the second page, open the first page by pressing F1, close the second page using the button on the first page, and close the first page by pressing F1.
Problem Author: Eugene Kurpilyanskiy (idea by Stanislav Vasilyev)
Problem Source: Ural Championship 2011