Tian Ji -- The Horse Racing

# 田忌——赛马 时间限制: $5000$ms 内存限制: $65536$KB ## 题目描述 这是中国历史上的一个著名故事。 那是 $2300$ 年前的事了。田忌将军是齐国的一位高级官员。他喜欢和国王以及其他人一起赛马。 田和王都有三匹不同等级的马，即普通马、加号马和超级马。规则是一场比赛有三轮;每匹马必须用一轮。单轮比赛的获胜者从失败者那里得到 $200$ 银元。 作为这个国家最有权势的人，国王的马非常好，每个阶层的马都比田的好。结果，国王每次都从田那里得到六百银元。 田忌对此并不高兴，直到他遇到了孙膑，中国历史上最著名的将军之一。在接下来的比赛中，田忌耍了个小把戏，赢回了 $200$ 块银元，赢得了这样一场比赛的胜利。 这是一个相当简单的把戏。用他的常规班赛马来对抗国王的超级班马，他们肯定会输掉那一轮。但是他的加号马打败了国王的正加号马，他的超级加号马打败了国王的正加号马。多么简单的把戏。你认为中国的高级官员田忌怎么样? 如果田忌生活在现在，他一定会嘲笑自己。而且，如果他现在参加 ACM 竞赛，他可能会发现赛马问题可以简单地看作是在一个二部图中找到最大匹配。一边画田的马，另一边画王的马。每当田的一匹马能从王那里打败一匹马时，我们就在这匹马之间划一道边线，这意味着我们希望建立这匹马。然后，赢得尽可能多的回合的问题就是在这个图中找到最大匹配。如果有联系，问题就变得更复杂了，他需要给所有可能的边分配权重 $0$、$1$ 或 $-1$，并找到一个最大的加权完美匹配。 然而，赛马问题是一个非常特殊的两部分匹配的情况。这个图是由马的速度决定的——一个速度高的顶点总是打败一个速度低的顶点。在这种情况下，加权二分匹配算法是一个过于先进的工具来处理这个问题。 在这个问题中，你被要求编写一个程序来解决这个特殊的匹配问题。 ## 输入 输入由多达 $50$ 个测试用例组成。每一种情况都从第一行的正整数 $n(n\le1000)$ 开始，这是每边的马的数量。第二行接下来的 $n$ 个整数是田的马的速度。第三行接下来的 $n$ 个整数是国王的马的速度。在最后一个测试用例之后，输入以一行 `0` 结束。 ## 输出 对于每个输入用例，输出一行包含单个数字的行，这是这天将获得的最大金额，以银元表示。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=446&page=show_problem&problem=4090 [PDF](https://uva.onlinejudge.org/external/13/p1344.pdf)

3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0

200
0
0