问题 1949. -- 田忌赛马

1949: 田忌赛马

时间限制: 1 Sec  内存限制: 128 MB
提交: 47  解决: 12
[提交][状态][讨论版]

题目描述

中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了,他们各派出n匹马,每场比赛,输的一方将要给赢的一方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

提示

来源

[提交][状态]