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$ 種操作入面揀一個或以上嘅操作，再按自己鍾意嘅次序執行。同一種操作可以做兩次或以上。第 $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$ 種。
• 跟住 $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

說明

一開始，卡牌排列係 IOOIIIOOOOIIIII。

做第 2 種操作後，會變成 IIIOOOOOOOIIIII。呢個操作需要 5 秒。

再做第 3 種操作後，會變成 IIIIIIIIIIIIIII，令占卜成功。呢個操作需要 7 秒。

用 12 秒就可以令占卜成功。呢個係最短時間，所以輸出 12。

輸入格式 2

1 1 1 1 1
1
1 1

輸出格式 2

-1

說明

呢個範例冇可能令占卜成功，所以輸出 -1。