Description

In player A’s space war game, a powerful mothership often decides the outcome of a war. The attack power of a mothership cannot be matched by ordinary MAs (Mobile Armor).

A mothership consists of several attack systems and several defense systems. When two motherships duel, one mothership will choose different attack systems to attack the opponent’s defense systems. If the attack power of an attack system is greater than the defense power of a defense system, that defense system will be destroyed. After all defense systems of a mothership have been destroyed, all remaining attacks will hit the enemy mothership itself and deal damage.

In other words, the damage a mothership deals to the opponent depends, to some extent, on how you choose targets.

On a rapidly changing battlefield, choosing optimal targets is crucial. Therefore, you need to implement a battle system to determine the maximum damage your mothership can deal to the opponent.

Input Format

The first line contains two integers $M$ and $N$, the number of the opponent’s defense systems and the number of your mothership’s attack systems.

Then follow $M$ lines, each with one integer, representing the defense power of each opponent defense system.

Then follow $N$ lines, each with one integer, representing the attack power of each of your attack systems.

Output Format

Output a single line with the maximum damage that can be dealt.

3 5 
1000 
2000 
1200 
2100 
2000 
1200 
1000 
1000

2000

Hint

Sample Explanation #1

The opponent has $3$ defense systems with defense values $1000(a),2000(b),1200(c)$, and you have $5$ attack systems with attack values $2100(d),2000(e),1200(f),1000(g),1000(h)$. An optimal plan for the first round is: $d$ attacks $b$, $e$ attacks $c$, $f$ attacks $a$, and $g$ and $h$ attack the enemy mothership itself, dealing $2000$ damage.

Constraints

For $80 \%$ of the testdata, $1 \le N,M \le 1000$.

For $100 \%$ of the testdata, $1 \le N,M \le 10 ^ 5$.

This problem is a reposted problem.

Translated by ChatGPT 5