Barn Numbering Alignment

Farmer John owns N barns (3 \leq N \leq 5\cdot10^5). Two workers, Annabelle and Bessie, each assign a permutation of the numbers from 1 to N onto the barns. Annabelle observed that the barns assigned the numbers \(a_1, a_2, \dots, a_K\) (all distinct) form a cycle; that is, for every \(1 \le i < K\), barn \(a_i\) is connected to barn \(a_{i+1}\), and barn \(a_K\) is connected to barn \(a_1\). Similarly, Bessie found that barns labeled \(b_1, b_2, \dots, b_K\) (all distinct) form another cycle (with barn \(b_K\) connected to barn \(b_1\)).

Some barns may receive the same number in both assignments. Your task is to compute the maximum possible number of barns that could have been assigned the same number by both Annabelle and Bessie. It turns out that apart from the cycle barns, any barn can be freely assigned the same number in both assignments. Hence, the optimal strategy is to assign the same numbers to all the remaining N-K barns. For the cycle barns, you can choose a cyclic rotation for one of the cycles, and then the number of matches will be the number of indices \(i\) for which \(a_i = b_{(i+\text{shift}) \;\%\; K}\). Therefore, the answer is:

[ \text{answer} = N - K + \max_{0 \leq s < K} ; \Big{ #{i \mid 0 \leq i < K,; a_i = b_{(i+s) \bmod K}} \Big} ]

Note that rather than brute forcing over all shifts (which is too slow when \(K\) is large), an efficient method is possible: for each barn number that appears in Annabelle's cycle, if it also appears in Bessie's cycle then the shift needed to align that number is \((j-i) \bmod K\) (where \(i\) and \(j\) are the positions in \(a\) and \(b\), respectively). Counting the frequency of each shift yields the maximum number of matches.

inputFormat

The first line contains two integers \(N\) and \(K\), where \(N\) is the total number of barns and \(K\) is the length of the cycle.

The second line contains \(K\) distinct integers \(a_1, a_2, \dots, a_K\) representing the cycle in Annabelle's assignment.

The third line contains \(K\) distinct integers \(b_1, b_2, \dots, b_K\) representing the cycle in Bessie's assignment.

outputFormat

Output a single integer, the maximum possible number of barns that could have the same number in both assignments.

sample

7 3
1 2 3
3 1 4

5