#941. 赛马

赛马

样例下载

题目描述

WhiteWhite 有 NN 匹白马,编号为 11 ~ NN。每匹马有一个马力值,编号为 ii 的白马的马力值为 WiW_i。

BlackBlack 有 NN 匹黑马,这些黑马围成一圈,按顺时针依次编号为 11 ~ NN。NN 号黑马的顺时针方向下一匹马为 11 号黑马。每匹马有一个马力值,编号为 ii 的黑马的马力值为 BiB_i。

现在 WhiteWhite 和 BlackBlack 要进行跑马比赛。比赛共分 NN 场,每场比赛双方各派出一匹马进行角逐,马力值大的一方将获胜。每匹马仅允许上场一次。

WhiteWhite 首先为他的每匹马分配了一个期望对手。编号为 ii 的白马期望对手是编号为 CiC_i 的黑马。

不过可能有多匹白马分配了同一匹黑马对手。这不符合比赛规则。每匹马只能上场一次。于是 WhiteWhite 需要修改他的分配策略。

经过调整,WhiteWhite 作出了如下策略:

WhiteWhite 选择一匹尚未分配对手的白马,假设其编号为 xx,让它去和期望对手 CxC_x 比赛;但如果 CxC_x 已经匹配了对手,则 WhiteWhite 会顺时针尝试匹配下一匹黑马;如果下一匹黑马尚未分配对手,则 xx 与其匹配成功,否则 WhiteWhite 会继续顺时针尝试匹配下一匹黑马,直到匹配成功。

WhiteWhite 不断重复以上匹配方式,直到所有马匹配成功。

问:WhiteWhite 如何为自己的白马分配对手,可以使得自己获胜场次最多?

你只需要输出 WhiteWhite 最多能获胜多少场。

输入格式

第一行:包含一个整数 NN。

第二行:包含 NN 个整数 CiC_i;

第三行:包含 NN 个整数 BiB_i;

第四行:包含 NN 个整数 WiW_i;

数据保证不管黑马白马都不存在相同的马力值。

输出格式

一个整数,表示答案。

样例 1 输入

3
2 3 3
4 1 10
2 7 3

样例 1 输出

2

样例 2 输入

4
3 1 3 3
5 8 7 10
4 1 2 6

样例 2 输出

1

样例 3 输入

3
1 2 3
8 4 3
9 2 6

样例 3 输出

2

样例 4 输入

6
1 4 4 4 2 5
1 22 3 444 5 666
7 88 9 10 111 12

样例 4 输出

4

数据范围

40% 的数据:Ci=1C_i = 1;

100% 的数据:1≤N≤5×1051 ≤ N ≤ 5 \times 10 ^ 5,1≤Bi,Wi≤1091 ≤ B_i, W_i ≤ 10 ^ 9。输入数据保证 2N2N 个马力值两两不同。