P1650 Tian Ji’s Horse Racing

There is a famous story in Chinese history: it was about $2300$ years ago. General Tian Ji of the State of Qi loved horse racing. He often raced horses with the King of Qi. Each of them had three horses: a regular-grade horse, an upper-grade horse, and a super-grade horse. They raced three times in total, and in each race the winner could take $200$ silver coins from the loser. Each horse could be used only once. The King’s horses were better; within the same grade, the King’s horse was always slightly better than Tian Ji’s. So every time he raced the King, Tian Ji would lose $600$ silver coins. Tian Ji was very frustrated until he met the famous strategist — Sun Bin. After adopting Sun Bin’s plan, Tian Ji easily and gracefully won $200$ silver coins from the King of Qi over three races. The strategy was very simple. Since the King always sent out his best horse first and then his second best, Tian Ji used his regular-grade horse against the King’s super-grade horse, his super-grade horse against the King’s upper-grade horse, and his upper-grade horse against the King’s regular-grade horse, achieving two wins and one loss to gain $200$ silver coins. It was indeed simple. What if there are more than three horses? This problem can obviously be transformed into a bipartite optimal matching problem. Put Tian Ji’s horses on the left and the King’s horses on the right. Between Tian Ji’s horse A and the King’s horse B, if Tian Ji’s horse wins, add an edge with weight $200$; if it is a draw, add an edge with weight $0$; if it loses, add an edge with weight $-200$... If you do not know how to compute the optimal matching, you can also use minimum-cost maximum flow. However, the horse racing problem is a special case of bipartite optimal matching, and the above algorithms are overkill. Now, please design a simple algorithm to solve this problem.

The first line contains an integer $n$, indicating how many horses each of them has (both have the same number of horses). The second line contains $n$ integers, each representing the speed value of one of Tian Ji’s horses (each speed value is between $0$ and $100$ inclusive). The third line contains $n$ integers, describing the speed values of the King’s horses. When two horses meet, the winner is determined by the comparison of their speed values. If the speed values are equal, it is a draw and no one takes any money.

Output a single line containing one integer: the maximum number of silver coins Tian Ji can obtain.

### Constraints and Conventions - For $20\%$ of the testdata, $1 \le n \le 65$. - For $40\%$ of the testdata, $1 \le n \le 250$. - For $100\%$ of the testdata, $1 \le n \le 2000$. Translated by ChatGPT 5