题目描述

K 理事长喜欢占卜，总是进行各种各样的占卜。今天，他使用了正面写有 ‘T’、背面写有 ‘O’ 的卡片，来占卜今年 IOI 日本代表队的表现。

占卜的方法如下：

1. 首先，确定正整数 $A, B, C, D, E$。
2. 将 $A + B + C + D + E$ 张卡片横向排列成一行。排列方式为：从左开始，前 $A$ 张为正面，接着 $B$ 张为背面，接着 $C$ 张为正面，接着 $D$ 张为背面，最后 $E$ 张为正面。这样排列后，从左到右依次会出现 $A$ 个 ‘T’、$B$ 个 ‘O’、$C$ 个 ‘T’、$D$ 个 ‘O’、$E$ 个 ‘T’。
3. 从预先确定的 $N$ 种操作中选择一种或多种，按任意顺序执行。允许对同一种操作执行多次。第 $i$ 种（$1 \le i \le N$）操作定义为：“将从左数第 $L_i$ 张到第 $R_i$ 张卡片的所有正反面翻转”。翻转一张卡片需要 1 秒钟，因此执行第 $i$ 种操作需要 $R_i - L_i + 1$ 秒。
4. 操作结束后，若所有卡片都为正面，则占卜成功。

为了尽可能减少实际翻转卡片的次数，K 理事长在实际占卜前，希望先判断是否有可能使占卜成功。如果可以成功，他还希望求出使占卜成功所需的最少时间。

题目

给定卡片的初始排列信息和预先确定的操作信息，编写程序判断是否可以使占卜成功；如果可以，求出使占卜成功所需的最少时间。

输入格式

从标准输入读入以下数据：

• 第一行包含五个整数 $A, B, C, D, E$，以空格分隔。这表示占卜开始时，从左到右依次排列 $A$ 张正面、$B$ 张背面、$C$ 张正面、$D$ 张背面、$E$ 张正面的卡片。
• 第二行包含一个整数 $N$，表示预先确定的操作种类数。
• 接下来的 $N$ 行，第 $i$ 行（$1 \le i \le N$）包含两个整数 $L_i, R_i$，以空格分隔。这表示第 $i$ 种操作为“将从左数第 $L_i$ 张到第 $R_i$ 张卡片的所有正反面翻转”。

输出格式

如果可以使占卜成功，则在标准输出上输出一行，表示使占卜成功所需的最少时间的整数；否则，输出 $-1$。

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

12

1 1 1 1 1
1
1 1

-1

提示

样例 1 解释

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

数据范围

所有输入数据均满足以下条件：

• $1 \le A \le 100000$
• $1 \le B \le 100000$
• $1 \le C \le 100000$
• $1 \le D \le 100000$
• $1 \le E \le 100000$
• $1 \le N \le 100000$
• $1 \le L_i \le R_i \le A + B + C + D + E$（$1 \le i \le N$）

子任务

子任务 1 [15 分]

• $N \le 10$

子任务 2 [50 分]

满足以下条件：

• $1 \le A \le 50$
• $1 \le B \le 50$
• $1 \le C \le 50$
• $1 \le D \le 50$
• $1 \le E \le 50$

子任务 3 [35 分]

• 无额外限制

翻译由 Qwen3-235B 完成