#P6866. 智者

    ID: 6697 传统题 1500ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-图论差分约束排序与序列处理一维前缀和自定义排序规则最长上升子序列动态规划线性 DP离散化数据结构树状数组CF2700

智者

智者

题目描述

小 D 听了一个故事。

这个故事是著名的红蓝眼睛问题在更多颜色情况下的拓展(如果你并不清楚红蓝眼睛问题,这并不影响你做题):

在一个岛上,有NN个极端聪明的智者,每个人头上都有一个帽子,上面有一个介于[1,105][1,10^5] 之间的数字。这里的数值范围限制输入,推理时不作为智者已知条件,候选帽子数字取全体整数。每个人能看到其他所有人帽子上面的数字,但是唯独看不到自己的。不会有任何两个智者交流与帽子上的数字有关的话题。

由于一些宗教因素,我们称一个 {a}\{a\} 是合法的,当且仅当∃i∈{1,…,N−1}\exists i\in\{1,\ldots,N-1\}, 使得 ai+1<ai+bia_{i+1}<a_{i}+b_{i},或者 ai+1>ai+cia_{i+1}>a_{i}+c_{i},其中 {b}\{b\} 和 {c}\{c\} 都是给定的序列。智者们都已知现在的数字序列一定是合法的。

每天,如果存在一个智者ii,他知道了一个数字 xx,使得 aia_{i} 一定不为 xx,那么他会立即宣布这一事件,并且这一过程结束。如果没有这样的智者, 那么这一天将会结束,并进入下一天。

小 D 想要知道,这个过程会在第几天结束,或者会永远进行下去。 但是小 D 并不会,请你帮帮他。

输入格式

从标准输入读入数据。

第一行一个正整数 NN,表示智者的个数。 第二行NN个空格隔开的正整数,其中第ii个数为aia_{i}。 第三行 N−1N-1 个整数,其中第ii个数为bib_{i}。 第四行 N−1N-1 个整数,其中第ii个数为cic_{i}。

输出格式

向标准输出输出答案。

输出一行一个整数,表示结束的天数。特别地,如果永远不会结束,请输出

−1-1。

样例1输入

3
1 2 3
0 0
0 0

样例1输出

2

数据范围

对于所有测试数据,$1\le N\le 3\times 10^{5},1\le a_{i}\le 10^{5},-10^{5}\le b_{i},c_{i}\le 10^{5}$, 保证输入的 {a}\{a\} 是合法的。

• Subtask 1(30%):N≤5000N\le 5000;

• Subtask 2(40%):N≤105N\le 10^{5};

• Subtask 3(30%):无特殊限制。