题目描述

基希讷乌，摩尔多瓦的首都，有两支各由 $N$ 名球员组成的足球队，进行一系列的对决。为了增加趣味，他们按照以下一对一的方式安排比赛：

• 总共有 $N$ 场对决，每场在不同的体育场进行。
• 每场对决将有两队中的一名球员对决。
• 每个球员将只参加一场对决。
• 每个体育场将为各自的对决胜利者提供一定金额的奖金。
• 技能等级更高的球员赢得对决。保证总有技能等级更高的球员。

在所有比赛结束后，冠军队是获得奖金总额超过对方球队的队伍。如果获得的奖金相同，则没有冠军。

你是第一支球队的经理，你的任务是安排你的 $N$ 名球员参加 $N$ 场对决获得冠军。

作为第一支足球队的经理，你拥有以下信息：

• $N$ 个整数，表示你队伍中球员的技能等级
• $N$ 个整数，表示对方队伍中球员的技能等级

作为经理，你还派了一名侦查员访问每个体育场。侦查员按从 $1$ 到 $N$ 的顺序访问体育场，首先访问体育场 $1$，然后是体育场 $2$，最后访问体育场 $N$。侦查员访问完体育场 $i$ 后，他会向你报告对方球队在体育场 $i$ 的对决球员的技能等级。

可能在侦查员访问了一些体育场之后，你已经可以预见你的球队将成为冠军。换句话说，有可能在侦查员访问了一些体育场后，你可以确定你能成为冠军。你可能仍然需要等待侦查员访问剩余的体育场，以便为你的球队建立分配方案。

你的任务是找出侦查员需要访问的最少体育场数量，以确保你的球队能够夺冠，或者确定不可能成为冠军。

输入格式

第一行，一个正整数 $N$；

第二行 $N$ 个整数 $p_1,p_2,\dots,p_N$，表示体育馆的奖金数。

第三行 $N$ 个整数 $b_1,b_2,\dots,b_N$，其中 $b_i$ 表示对方球队在第 $i$ 个体育馆派出球员的足球水平。

第四行 $N$ 个整数 $a_1,a_2,\dots,a_N$，表示你的队员的足球水平。

输出格式

输出一个整数，表示你需要了解的体育场的最少数量，以确保你的球队能够成为冠军。

此外，如果你立即知道你的球队在任何情况下都会成为冠军，应该输出 $0$；即使在你了解所有 $N$ 个体育场的信息后，仍然无法找到获胜策略，那么输出 $-1$。

5
1 5 4 3 1
5 9 3 12 8
1 10 4 2 6

3

6
6 1 21 22 23 24
1 12 6 8 10 11
2 3 4 5 7 9

2

3
1 1 3
3 4 6
2 1 7

0

3
1 1 3
3 4 6
2 1 5

-1

提示

【样例 #1 解释】 对于第一个样例，在侦查员分享体育场 $1$ 和 $2$ 的信息后，你仍不能保证成为冠军。原因是，如果对手按以下方式安排球员：

体育场	$1$	$2$	$3$	$4$	$5$
奖金	$1$	$5$	$4$	$3$	$1$
对手球员技能等级	$5$	$9$	$8$	$12$	$3$

你最好的选择是打成平局：

体育场	$1$	$2$	$3$	$4$	$5$
你的球员技能等级	$6$	$10$	$1$	$2$	$4$

你将赢得体育场 $1,2,5$ 的比赛，获得奖金总额 $1+5+1=7$，而对手将赢得体育场 $3,4$ 的比赛，获得奖金总额 $4+3=7$。

在侦查员分享体育场 $1,2,3$ 的信息后，你可以确定你将成为冠军。原因是，如果对手按以下方式安排球员：

体育场	$1$	$2$	$3$	$4$	$5$
奖金	$1$	$5$	$4$	$3$	$1$
对手球员技能等级	$5$	$9$	$3$	未知

对手的两种选择是：

体育场	$1$	$2$	$3$	$4$	$5$
奖金	$1$	$5$	$4$	$3$	$1$
对手球员技能等级	$5$	$9$	$3$	$12$	$8$
你的球员技能等级	$6$	$10$	$4$	$1$	$2$

体育场	$1$	$2$	$3$	$4$	$5$
奖金	$1$	$5$	$4$	$3$	$1$
对手球员技能等级	$5$	$9$	$3$	$8$	$12$
你的球员技能等级	$6$	$10$	$4$	$1$	$2$

我们可以注意到，在这两种情况下，我们的球队将在体育场 $1,2,3$ 获胜，获得奖金总额 $1+5+4=10$，而对手将获得奖金总额 $3+1=4$。由于 $10>4$，我们可以确定在这两种情况下我们都会获胜，因此最小答案是 $3$。

【样例 2 解释】 对于第二个样例，可以证明，在侦查员提供体育场 $1,2$ 的信息后，你将首次确定成为冠军。然而，与第一个样例不同，你不会有一个固定的获胜分配。相反，对于对手在体育场 $3, 4, 5, 6$ 中的不同安排，你需要有不同的应对策略来赢得冠军。

【数据范围】

$\text{Subtask}$	分值	特殊性质
$1$	$12$	$p_i=1,N\le10$
$2$	$16$	$p_i=1$
$3$	$14$	答案为 $0$ 或 $1$
$4$	$18$	答案为 $-1$ 或 $N-1$
$5$	$10$	$n\le5$
$6$	$30$	无

对于 $100\%$ 的数据，$1 \le N \le 5 \times 10^4,1 \le a_i,b_i \le 10^6$，且所有 $a_i,b_i$ 两两不同。