Necklace

Frank the jeweller must assemble an exclusive necklace whose bead layout is fixed in advance. Each bead is gold (G), silver (S), or bronze (B); beads of the same colour are identical and interchangeable. The finished necklace is a closed loop: after assembly Frank joins the two ends of the string, and the join may sit between any two adjacent beads, so the layout is treated as cyclic.

Frank has already threaded all the beads onto a single straight pin, but the order may differ from the necklace. He assembles it by repeatedly taking the next bead off the left end of the pin and either:

• threading it directly onto either end of the partially built string, or
• setting it aside in a pile for later use.

At any time he may also take a bead of a needed colour from the pile and thread it onto either end of the string. Because his workshop is a mess and the beads are precious, Frank wants to minimise the largest number of beads that are ever in the set-aside pile at one time. A bead threaded straight from the pin onto the string never enters the pile.

Given the target layout and the order of the beads on the pin, determine that minimum.

The first line contains one integer $L$ ($1 \le L \le 1000$) — the number of beads. The second line is a string of $L$ characters (each G, S, or B) giving the necklace layout, cut at some point and straightened out (read cyclically). The third line is a string of $L$ characters giving the beads on the pin, in the order Frank removes them from the left end. It is guaranteed that the necklace can be assembled from the beads on the pin (the two strings contain the same multiset of colours).

Print a single integer: the minimum possible value of the largest set-aside pile size at any moment during assembly.

• In the first example the layout alternates gold and silver, so both neighbours of any bead have the opposite colour. Whichever silver bead Frank starts with, its two neighbours must be gold, but the pin delivers four silvers first; three of them have to wait in the pile until the golds arrive, so the pile reaches size 3.
• In the second example Frank can thread every bead straight from the pin: he grows the gold beads from one end of the string and the silver beads from the other, so nothing is ever set aside and the answer is 0.