RoAlgo Contest #11 - Back to School 2024 | costMin

Task

You are given two arrays $a$ and $b$ of length $n$ and $m$, respectively.

We define the cost of two arrays $x$ and $y$ of length $p$ and $l$ as follows:

1. For each $i$ from $1$ to $\min(p, l)$, add $1$ to the cost of the two arrays if $x_i \not= y_i$.
2. At the end, add to the cost of the two arrays the value $\max(p, l) - \min(p, l)$.

Your task is to find the minimum cost of the arrays $a$ and $b$ if you are allowed to swap any two elements from $a$ and $b$ (but you cannot change one element from $a$ with one element from $b$) as many times as you want.

Input data

The first line of the input contains two integers, $n$ and $m$. The second line contains the array $a$, of length $n$. The third line contains the array $b$, of length $m$.

Output data

The first line of the output will contain a single integer, the minimum cost after performing the swaps in the arrays $a$ or $b$.

Constraints and clarifications

• $1 \leq n, m \leq 2 \cdot 10^5$
• $1 \leq a_i \leq 10^6$, for $1 \leq i \leq n$
• $1 \leq b_i \leq 10^6$, for $1 \leq i \leq m$

Example

stdin

4 3
1 1 2 3
2 3 5

stdout

2

Explanation

You swap the pairs $(1, 3)$ and $(2, 4)$ from the array $a$, becoming $[2, 3, 1, 1]$ and the cost becomes $2$, because for each $i$ from $1$ to $\min(4, 3)$, there is only one position where $a_i \not= b_i$, which is $3$. Therefore, the cost becomes $1 + \max(4, 3) - \min(4, 3) = 1 + 4 - 3 = 2$.