Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

M. The World's Biggest São João
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Every year, one debate stirs Northeastern Brazil: after all, which is the world's biggest São João, the one in Campina Grande or the one in Caruaru?

To try to settle the matter, a research institute decided to run two polls: one during the São João festival in Campina Grande and another during the São João festival in Caruaru.

The $$$N$$$ interviewed people attended both festivals, experiencing both Campina Grande's São João and Caruaru's São João up close. However, for organizational reasons, each person took part in exactly one of the two polls.

It is allowed for one of the polls to be empty.

Each person has a true opinion about which festival they prefer: Campina Grande or Caruaru.

However, the polls happened in the middle of the party, with lots of forró, fireworks, and noise. Because of that, when a person said their answer, the institute could end up hearing it wrong. Thus, the vote recorded for a person may be different from their true opinion.

A few days later, each participant receives the result of the poll they joined: how many votes were recorded for Campina Grande and how many votes were recorded for Caruaru.

Each person's evaluation of the poll depends only on their true opinion:

  • for each vote recorded for the festival they prefer, their evaluation increases by $$$1$$$;
  • for each vote recorded for the other festival, their evaluation decreases by $$$1$$$.

The total score of a poll is the sum of the evaluations of all its participants.

Assuming each participant was assigned to a poll in a way that maximizes the sum of the scores, determine the largest possible sum of the scores of the two polls.

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 2 \times 10^{5}$$$), the number of interviewed people.

The second line contains a string $$$P$$$ of length $$$N$$$, where $$$P_i$$$ represents the true opinion of person $$$i$$$:

  • G indicates that they prefer Campina Grande's São João;
  • R indicates that they prefer Caruaru's São João.

The third line contains a string $$$V$$$ of length $$$N$$$, where $$$V_i$$$ represents the vote that was recorded for person $$$i$$$:

  • G indicates that the vote was recorded for Campina Grande;
  • R indicates that the vote was recorded for Caruaru.
Output

The output must contain only one integer, the largest possible sum of the scores of the two polls.

Examples
Input
4
GGRR
GRGR
Output
2
Input
3
GGG
GGG
Output
9
Note

Explanation for example 1

One optimal division is to put person $$$1$$$ in the first poll and people $$$2$$$, $$$3$$$, and $$$4$$$ in the second poll.

In the first poll, there is only person $$$1$$$. Their recorded vote was G, and they prefer G, so their evaluation is $$$1$$$. Therefore, the score of the first poll is $$$1$$$.

In the second poll, the recorded votes of people $$$2$$$, $$$3$$$, and $$$4$$$ are, respectively, R, G, and R. Thus, the result of this poll contains $$$1$$$ vote for Campina Grande and $$$2$$$ votes for Caruaru.

Person $$$2$$$ prefers G, so their evaluation is $$$1 - 2 = -1$$$.

Person $$$3$$$ prefers R, so their evaluation is $$$2 - 1 = 1$$$.

Person $$$4$$$ prefers R, so their evaluation is $$$2 - 1 = 1$$$.

Therefore, the score of the second poll is $$$-1 + 1 + 1 = 1$$$. The sum of the two poll scores is $$$1 + 1 = 2$$$, which is the maximum possible value.

Explanation for example 2

Everyone prefers Campina Grande, and all votes were recorded for Campina Grande.

One optimal division is to put all people in the same poll and leave the other poll empty.

In the poll with the three people, there are $$$3$$$ votes recorded for Campina Grande and $$$0$$$ votes recorded for Caruaru. Since everyone prefers Campina Grande, each of them has evaluation $$$3 - 0 = 3$$$.

Therefore, the score of this poll is $$$3 + 3 + 3 = 9$$$. The other poll is empty and contributes $$$0$$$ points.

Thus, the largest possible sum of scores is $$$9$$$.