{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e这是中国历史上的一个著名故事。\u003cbr\u003e\u003cbr\u003e“大约2300年前,田忌将军是齐国的高级官员。他喜欢和国王以及其他人一起进行赛马比赛。”\u003cbr\u003e\u003cbr\u003e“田忌和国王都有三匹不同级别的马,分别是普通、加强和超级。规则是比赛三轮,每匹马必须在一轮中参赛。每一轮的赢家从输家那里拿走两百两白银。”\u003cbr\u003e\u003cbr\u003e“作为国家最有权势的人,国王的马都比田忌的好。因此,每次国王都从田忌那里赢得六百两白银。”\u003cbr\u003e\u003cbr\u003e“田忌对此感到不满,直到他遇见了孙膑,中国历史上最著名的将军之一。在孙膑的小技巧帮助下,田忌带着两百两白银和下一场比赛的荣耀回家了。”\u003cbr\u003e\u003cbr\u003e“这是一个非常简单的技巧。他的普通级马与国王的超级级马比赛,肯定会输掉那一轮。但是他的加强级马击败了国王的普通级马,他的超级级马又击败了国王的加强级马。多么简单的技巧啊。你觉得田忌这位中国的高级官员怎么样呢?”\u003cbr\u003e\u003cbr\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/c4c9b604b2ccd9c212f3b05c47cda298?v\u003d1701314381\"\u003e\u003cbr\u003e\u003cbr\u003e如果田忌活在现在,他肯定会对自己大笑。更甚者,如果他现在坐在ACM竞赛中,他可能会发现赛马问题其实可以简单地看作是在二分图中找到最大匹配。把田忌的马放在一边,国王的马放在另一边。每当田忌的一匹马能击败国王的一匹马时,我们在它们之间画一条边,表示我们希望建立这对匹配。那么,尽可能多地赢得比赛的问题就是在这个图中找到最大匹配。如果出现平局,问题就变得更加复杂,他需要为所有可能的边分配权重0、1或-1,并找到最大权重的完美匹配……\u003cbr\u003e\u003cbr\u003e然而,赛马问题是二分图匹配的一个非常特殊的情况。这个图是由马的速度决定的——速度更快的顶点总是能击败速度较慢的顶点。在这种情况下,加权二分图匹配算法是一个处理这个问题的太高级的工具。\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"输入包括最多50个测试用例。每个用例以第一行上的一个正整数n(n \u0026lt;\u003d 1000)开始,表示每一方的马匹数量。接下来的第二行包含n个整数,表示田忌的马的速度。然后第三行包含n个整数,表示国王的马的速度。在最后一个测试用例之后,输入以一行包含单个数字0结束。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个输入用例,输出一行包含一个数字,表示田忌将会赢得的最大银元数量。\u003cbr\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n92 83 71\r\n95 87 74\r\n2\r\n20 20\r\n20 20\r\n2\r\n20 19\r\n22 18\r\n0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e200\r\n0\r\n0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}