11003 - 田忌赛马

中国古代的历史故事“田忌赛马”是为大家所熟知的。话说齐王和田忌又要赛马了,他们各派出 N 匹马,每场比赛,输的一方将要给赢的一方 200 两黄金,如果是平局的话,双方都不必拿出钱。现在每匹马的速度值是固定而且已知的,而齐王出马也不管田忌的出马顺序。请问田忌该如何安排自己的马去对抗齐王的马,才能赢取最多的钱?

Input

第一行为一个正整数 N(N \le 20) ,表示双方马的数量。

第二行有 N 个整数表示田忌的马的速度。

第三行的 N 个整数为齐王的马的速度。

Output

仅有一行,为田忌赛马可能赢得的最多的钱,结果有可能为负。

Examples

Input

3
92 83 71
95 87 74

Output

200
Time Limit 30 毫秒
Memory Limit 128 MB
Stats
上一题 下一题