#P1537. 小 X 玩游戏(game)

小 X 玩游戏(game)

题目描述

听完了故事,小 XX 又想去玩一会儿游戏了。 这是一个很奇特的单机游戏, 游戏规则如下:

游戏中一共有 4×n4 × n 张牌,每张牌上有一个数字, 这些数字恰好是 114×n4 × n 。一开始电脑会把这 4×n4 × n 张牌随机打乱,然后会发 2×n2 × n 张牌给小 XX 。那些剩下的 2×n2 × n 牌电脑会再打乱一次,然后排成一排展示给小 XX 看。而小 XX 需要做的就是将自己的 2×n2 × n 张牌也排成一排,与电脑展示的 2×n2 × n 张牌一一对应。

之后就开始评分了,对于前 nn 对牌(一对牌是指小 XX 的一张加上电脑的一张), 牌上数字小的一方获得一分; 而对于后 nn 对牌, 牌上数字大的一方获得一分。

例如当 n=3n=3 时, 共有 1212 张牌 , 牌上的数字是 111212 。 电脑打乱后,小 XX 拿到 66 张牌 ,假设是 11, 33, 44, 55, 77, 88 。 此时电脑手中还剩下 22, 66, 99, 1010, 1111, 1212 。同样假设电脑会将这 66 张牌按照 99, 1111, 66, 22, 1212, 1010 这样的顺序展示给小 XX 看。如果小 XX 是将 66 张牌按 11, 77, 55, 88, 44, 33 这么排的,那么小 XX 会获得 44 分。

11 对: 191 – 9 ,小 XX11 分, 电脑得 00

22 对: 7117 – 11 ,小 XX11 分, 电脑得 00

33 对: 565 – 6 ,小 XX11 分, 电脑得 00

44 对: 828 – 2 ,小 XX11 分, 电脑得 00

55 对: 4124 – 12 , 电脑得 11 分,小 XX00

66 对: 3103 – 10 , 电脑得 11 分,小 XX00

前一半第 11 对~第 33 对牌是比谁小,后一半第 44 对~第 66 对牌是比谁大。前一列数字代表的是小 XX 的牌,后一列数字代表的是电脑的牌。

XX 现在已经拿到了 2×n2 × n 张牌,同时电脑也已经展示出了它的 2×n2 × n 张牌是怎么排列的,小 XX 想知道他最多能够获得多少分?

输入

输入数据第一行为一个正整数 nn

接下来一行共有 2×n2 × n 个用空格隔开的正整数, 表示小 XX 手中拥有的 2×n2 × n 张牌。

再下一行同样是 2×n2 × n 个用空格隔开的正整数, 表示电脑展示出的 2×n2 × n 张牌(以读入的顺序展示)。

输出

输出一行只有一个数 ansans , 表示小 XX 最多能够获得的分数。

样例

4
5 3 2 16 14 13 9 7
1 8 12 11 15 6 4 10
7

说明

数据范围

对于 30%30\% 的数据, 1n41 ≤ n ≤ 4

对于另外 40%40\% 的数据, 电脑展示的 2×n2 \times n 张牌是从小到大排好序的;

对于 100%100\% 的数据, 1n10001 ≤ n ≤ 1000