P2813 Mothership

Guangdong Shantou Yuhuai Junior High School Train#3 Problem 1. (Does this give a Red Alert vibe?)

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.

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 a single line with the maximum damage that can be dealt.

#### 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