17719번 - IOIOI Cards 서브태스크다국어

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 ≦ i ≦ 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 ≦ i ≦ N) には，整数 L_i, R_i が空白を区切りとして書かれている．これは， i 種類目の操作が「左から L_i 枚目から R_i 枚目までのカードの表裏をすべてひっくり返す」という操 作であることを表す．

占いを成功させることが可能な場合は，占いを成功させるためにかかる時間の最小値を表す整数を標準 出力に 1 行で出力せよ．そうでない場合は，−1 を出力せよ．

• 1 ≦ A ≦ 100 000．
• 1 ≦ B ≦ 100 000．
• 1 ≦ C ≦ 100 000．
• 1 ≦ D ≦ 100 000．
• 1 ≦ E ≦ 100 000．
• 1 ≦ N ≦ 100 000．
• 1 ≦ L_i ≦ R_i ≦ A + B + C + D + E (1 ≦ i ≦ N)．

• N ≦ 10 を満たす．

• 1 ≦ A ≦ 50．
• 1 ≦ B ≦ 50．
• 1 ≦ C ≦ 50．
• 1 ≦ D ≦ 50．
• 1 ≦ E ≦ 50．

追加の制限はない．