Frequent Alphabet

Interview

Time limit1sMemory limit512 MB

Summary

Given two length-N strings S and T, choose one character from each column to maximize the count of the most frequent letter in the resulting password.

Level: Medium5 of 10
Topics: Greedy, Math, Implementation, Brute force
Solved: No attempts yet

Problem

Your social media account has just been hacked, and you are advised to change your password. You have two favorite strings S and T, each containing exactly N lowercase alphabets. You want the new password to be some combination of these two strings. Specifically, the new password P should contain N alphabets such that the ith character of P is either the ith character of S or the ith character of T.

For example, let S = "icyz" and T = "ixpc". There are 8 different possible new passwords you can choose: "icyz", "icyc", "icpz", "icpc", "ixyz", "ixyc", "ixpz", and "ixpc".

The score of a password P is defined as the number of occurrences of the most frequent alphabet in P. For example, let P = "icpc". The password "icpc" has one occurrence of 'i', two occurrences of 'c', and one occurrence of 'p'. The most frequent alphabet in P is 'c' with 2 occurrences. Therefore, the score of "icpc" is 2.

Given two strings S and T, your task is to find the highest score you can get for your new password.

Input

Input begins with a line containing an integer N (1 ≤ N ≤ 100 000), the length of the password. The next line contains a string S of N lowercase alphabets, your first favorite string. The next line contains a string T of N lowercase alphabets, your second favorite string.

Output

Output in one line an integer, the highest score you can get for your new password.

Examples3

Example 1
Input
```
4
icyz
ixpc
```
Expected output
```
2
```
Example 2
Input
```
11
goodluckfor
contestants
```
Expected output
```
3
```
Example 3
Input
```
14
helpiamtrapped
inanincfactory
```
Expected output
```
4
```