RoAlgo Contest #11 - Back to School 2024 | costMin

This was the problem page during the contest. Access the current page here.
Time limit: 0.5s Memory limit: 64MB Input: Output:

Task

You are given two arrays aa and bb of length nn and mm, respectively.

We define the cost of two arrays xx and yy of length pp and ll as follows:

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

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

Input data

The first line of the input contains two integers, nn and mm. The second line contains the array aa, of length nn. The third line contains the array bb, of length mm.

Output data

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

Constraints and clarifications

  • 1n,m21051 \leq n, m \leq 2 \cdot 10^5
  • 1ai1061 \leq a_i \leq 10^6, for 1in1 \leq i \leq n
  • 1bi1061 \leq b_i \leq 10^6, for 1im1 \leq i \leq m
# Points Constraints
1 40 1n,m5 0001 \leq n, m \leq 5\ 000
2 60 No additional constraints

Example

stdin

4 3
1 1 2 3
2 3 5

stdout

2

Explanation

You swap the pairs (1,3)(1, 3) and (2,4)(2, 4) from the array aa, becoming [2,3,1,1][2, 3, 1, 1] and the cost becomes 22, because for each ii from 11 to min(4,3)\min(4, 3), there is only one position where aibia_i \not= b_i, which is 33. Therefore, the cost becomes 1+max(4,3)min(4,3)=1+43=21 + \max(4, 3) - \min(4, 3) = 1 + 4 - 3 = 2.

Log in or sign up to be able to send submissions!