问题 L: 田忌赛马

问题 L: 田忌赛马

时间限制: 1 Sec  内存限制: 128 MB
提交: 11  解决: 2
[提交][状态][讨论版][命题人:]

题目描述

“你知道蝴蝶效应吗?”李旭琳问。

“是不是说某地上空一只小小的蝴蝶扇动翅膀而扰动了空气,长时间后可能导致遥远的彼地发生一场暴风雨?”小墨老师回答。

“是这样的,虽然我很快就要回到原来的时空了,但我在这个时空,已经或多或少地改变了历史,因为在我所知道的历史中,现在的你本来是没有和修罗王比试魔法的。不知你现在准备好了吗?”李旭琳说。

“虽然我和他在魔法上各有千秋,可是总体来说,他还是强过我的。”小墨老师显得没有信心。

“那么想想田忌赛马的故事吧。有时,有头脑比有实力更为重要。”李旭琳提示小墨老师。

“田忌赛马”是历史上有名地揭示如何善用自己的长处去对付对手的短处,从而在竞技中获胜的事例。当时田忌和齐王赛马,他们各派出N匹马(N≤2000)。每场比赛,输的一方将要给赢的一方200两黄金,如果是平局的话,双方都不必拿出钱。

每匹马的速度值是固定而且已知的,而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马,才能赢最多的钱?

输入

有多组数据,每一组数据第一行为一个正整数N (N≤1000) ,表示双方马的数量。第二行有N个整数表示田忌的马的速度。第三行的N个整数为齐王的马的速度。全部数据结束以0表示。

输出

每组数据输出一行,为田忌赛马可能赢得的最多的钱,结果有可能为负。

样例输入

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

样例输出

200
0
0

提示

[提交][状态]