分数: 600 点
问题陈述
有 N 盒。 对于 i = 1, 2, \ldots, N, i第一个盒子包含 A_i 红球和 B_i 蓝色球。
你还得到了两种排列 P = (P_1, P_2, \ldots, P_N) 和 Q = (Q_1, Q_2, \ldots, Q_N) of (1, 2, \ldots, N).
Takahashi 可以重复以下操作任意次数,可能为零:
- 选择一个整数 1 \leq i \leq N,并从 i第一个盒子到了他手里。
- 将手中的红球全部放入 P_i第一个盒子。
- 将他手中的蓝色球全部放入 Q_i第一个盒子。
他的目标是让除 X重复上述操作,第一个盒子里没有球。 确定是否有可能实现他的目标,如果可能,打印实现该目标所需的最少操作数。
约束
- 2 \leq N \leq 2 \times 10^5
- 0 \leq A_i, B_i \leq 1
- 1 \leq P_i, Q_i \leq N
- P 和 Q 是排列 (1, 2, \ldots, N).
- 1 \leq X \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N X A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N P_1 P_2 \ldots P_N Q_1 Q_2 \ldots Q_N
输出
如果高桥不可能达到除 X第一个盒子不含球,打印 -1。如果可能,请打印实现该目标所需的最少操作数。
示例输入 1
5 3 0 1 0 1 0 0 0 1 0 1 4 1 2 3 5 3 4 5 2 1
示例输出 1
4
每个盒子里红球和蓝球的数量是 分别为 A = (0, 1, 0, 1, 0) 和 B = (0, 0, 1, 0, 1)。 考虑以下步骤:
- 首先,对第5个框进行操作。结果, A = (0, 1, 0, 1, 0), B = (1, 0, 1, 0, 0).
- 接下来,对第二个框执行操作。结果, A = (1, 0, 0, 1, 0), B = (1, 0, 1, 0, 0).
- 然后,对第一个框执行操作。结果, A = (0, 0, 0, 2, 0), B = (0, 0, 2, 0, 0).
- 最后执行第4个框的操作。结果, A = (0, 0, 2, 0, 0), B = (0, 0, 2, 0, 0).
这四个操作实现了除 X第(第三)个盒子不含球。 这是可能的最小操作数。
示例输入 2
5 3 0 0 0 0 0 0 0 0 0 0 4 1 2 3 5 3 4 5 2 1
示例输出 2
0
所有盒子里都没有球。 因此,除了 X已实现第(第 3)个盒子不含球,因此所需的操作次数为 0.
示例输入 3
2 2 1 1 1 1 1 2 1 2
示例输出 3
-1
无法执行操作来实现除 X第(第二)个盒子不含球。
示例输入 4
10 10 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 4 9 5 8 2 3 6 10 7 7 4 9 10 6 3 1 2 8 5
示例输出 4
8