K 理事長は占いが好きで，いつも様々な占いをしている．今日は，表の面に ‘I’ が，裏の面に ‘O’ が書かれたカードを使って今年の IOI での日本選手団の出来を占うことにした．

占いの方法は次のようなものである．

1. まず，正の整数 $A,B,C,D,E$ を決める．
2. $A+B+C+D+E$ 枚のカードを横 1 列に並べる．このとき，左から $A$ 枚は表，続く $B$ 枚は裏，続く $C$ 枚は表，続く $D$ 枚は裏，続く $E$ 枚は表にして並べる．このように並べると，左から順に ‘I’ が $A$ 個，‘O’ が $B$ 個，‘I’ が $C$ 個，‘O’ が $D$ 個，‘I’ が $E$ 個並ぶことになる．
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$ を出力せよ．

制約

すべての入力データは以下の条件を満たす．

• $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$ を出力する．