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

占卜的方法如下：

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 种或多种操作，按任意顺序执行。此时，同一种操作可以执行 2 次以上。第 $i$ 种操作 ($1 \le i \le N$) 为“将从左起第 $L_i$ 张到第 $R_i$ 张卡片的正反面全部翻转”。翻转 1 张卡片需要 1 秒。因此，执行第 $i$ 种操作需要 $R_i - L_i + 1$ 秒。
4. 操作结束后，如果所有卡片都变为正面，则占卜成功。

K 理事长为了避免不必要的翻转，决定在实际使用卡片占卜之前，先求出是否能够使占卜成功。此外，如果能够成功，求出使占卜成功所需的最短时间。

题目描述

给定卡片的排列信息和预先确定的操作信息。求出是否能够使占卜成功，如果可以，求出使占卜成功所需的最短时间。

输入格式

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

• 第 1 行包含空格分隔的整数 $A, B, C, D, E$。这表示占卜开始时，从左起 $A$ 张为正面，接着 $B$ 张为背面，接着 $C$ 张为正面，接着 $D$ 张为背面，接着 $E$ 张为正面。
• 第 2 行包含整数 $N$。这表示预先确定的操作有 $N$ 种。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含空格分隔的整数 $L_i, R_i$。这表示第 $i$ 种操作为“将从左起第 $L_i$ 张到第 $R_i$ 张卡片的正反面全部翻转”。

输出格式

如果能够使占卜成功，输出使占卜成功所需的最短时间（整数）；否则，输出 -1。

数据范围

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

• $1 \le A \le 100\,000$
• $1 \le B \le 100\,000$
• $1 \le C \le 100\,000$
• $1 \le D \le 100\,000$
• $1 \le E \le 100\,000$
• $1 \le N \le 100\,000$
• $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 点] * 无额外限制。

样例

输入样例 1

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

输出样例 1

12

说明 1

最初卡片排列为 IOOIIIOOOOIIIII。 执行第 2 种操作后，变为 IIIOOOOOOOIIIII。该操作耗时 5 秒。 接着执行第 3 种操作，变为 IIIIIIIIIIIIIII，占卜成功。该操作耗时 7 秒。 总共耗时 12 秒使占卜成功。这是最小值，因此输出 12。

输入样例 2

1 1 1 1 1
1
1 1

输出样例 2

-1

说明 2

在该输入样例中，无法使占卜成功，因此输出 -1。