You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小Y是占卜好手，他精通各种形式的占卜。今天，他要用正面写着 I ，背面写着 O 的卡片占卜他的运势。

占卜的方法如下：

1. 首先，选取五个正整数 $A,B,C,D,E$；
2. 然后，拿出 $A+B+C+D+E$ 张卡片摆成一排，从左至右摆成 $A$ 张正面，$B$ 张反面，$C$ 张正面，$D$ 张反面，$E$ 张正面的形式。也就是说，从左到右依次摆 $A$ 张 I，$B$ 张 O，$C$ 张 I，$D$ 张 O，$E$ 张 I；
3. 再从预先确定的 $N$ 种操作中选择 $1$ 种及以上，然后按照自己喜欢的顺序进行操作，同样的操作可以进行 $1$ 次及以上。第 $i$ 种操作是「把从左到右第 $L_i$ 张卡片到第 $R_i$ 张卡片（包括两端）翻过来」，因为需要用手操作，所以翻 $1$ 张牌需要花费 $1$ 秒，完成一次操作需要花费 $R_i-L_i+1$ 秒；
4. 操作后，如果所有牌都是正面朝上的，占卜就结束了。

因为这种占卜比较费时，所以小Y在占卜之前想知道占卜能否结束，如果能结束，他想知道占卜的最小耗时。

输入格式

第一行，五个正整数 $A,B,C,D,E$，意义如题目描述；

第二行，一个正整数 $N$，意义如题目描述；

接下来 $N$ 行描述操作，一行两个正整数 $L_i,R_i$，意义如题目描述。

输出格式

输出一行，如果占卜能够结束，则输出一个正整数，表示占卜的最小耗时；如不能，输出 $-1$。

样例

1 2 3 4 5
3
2 3
2 6
4 10

12

样例1解释

最初的卡片序列为 IOOIIIOOOOIIIII； 先进行第二个操作，卡片序列变为 IIIOOOOOOOIIIII，花费 $5$ 秒； 再进行第三个操作，卡片序列变为 IIIIIIIIIIII，这个操作花费 $7$ 秒，一共花费 $12$ 秒。 可以证明，$12$ 秒为占卜的最小耗时，因此输出 $12$。

1 1 1 1 1
1
1 1

-1

提示

对于全部测试点，满足 $1\le A,B,C,D,E,N\le 10^5,1\le L_i\le R_i\le A+B+C+D+E$。

具体子任务限制及分数如下表：