题目描述

你一定听过田忌赛马的故事吧？ 如果3匹马变成1000匹，齐王仍然让他的马按从优到劣的顺序出赛，田忌可以按任意顺序选择他的赛马出赛。赢一局，田忌可以得到200两银子，输一局，田忌就要输掉200两银子，平局的话不输不赢。 请问田忌最多能赢多少银子?

关于输入

输入包含多组测试数据. 每组测试数据的第一行是一个整数n(1<=n<=1000),表示田忌和齐王都拥有n匹马。接下来一行是n个整数，表示田忌的马的速度，下一行也是n个整数，表示齐王的马的速度。 输入的最后以一个0表示结束。

关于输出

对每组数据，输出一个整数，表示田忌至多可以赢多少银子，如果田忌赢不了，就输出一个负数，表示田忌最少要输多少银子。

例子输入

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

例子输出

200 0 0

解题分析

本题适合使用贪心算法，显然，我们要让田忌最小程度上亏损。先把田忌和齐王的马从小到大排序，然后从他们最强的马开始比起。如果田忌最强的马比齐王最强的马速度更快，则这局胜利。如果更弱呢？那肯定要输了，但是我们让田忌最弱的马去拼（这样损失最小）。如果一样强呢？那也肯定不能随便平局，我们就看看二者最弱的马，如果田忌最弱的马胜于齐王最弱的马，则先赢一把，然后找到一个田忌最弱的马速度也小于等于齐王最强的马，如果此时最弱的马要弱于齐王最强的马，则此局输。如果还是等于，则平局。我们采用双指针来模拟这个过程。

Limitation

1s, 1024KiB for each test case.