UOJ Logo

NOI.AC

1S 512MB

#1696. 田忌赛马

Statistics

题目描述

齐国的将军田忌经常同齐威王赛马。 他们赛马的规矩是:

当两匹马比赛时,速度值大的一方会获胜,胜的一方赢$1$两黄金,输的一方赔$1$两黄金。如果两马匹的$速度值$相同,则为平局,双方都不赚不赔。当然,同一匹马只能比赛一次

现知道齐威王和田忌两人的所有马的速度值。并且齐威王总是按速度从大到小的顺序出马,希望你给出一种最优策略,并求出田忌最多能赢(或者最少赔)多少钱。

输入格式

第一行:一个整数N,表示双方各有N匹马

第二行:N个正整数,分别表示齐威王每匹马的速度值

第三行:N个正整数,分别表示田忌每匹马的速度值。

输出文件

只有一个整数,表示田忌最多赢(最少赔)多少两黄金。

样例输入1

3
2 4 6
1 3 5

样例输出1

1

样例输入2

10
3 6 1 7 6 3 6 2 2 10
2 1 1 5 1 2 3 2 1 10

样例输出2

-1

数据范围

$N \le 5000$

$0 \le 速度值 \le 500$