Ketua K menyukai ramalan dan selalu mencoba berbagai cara meramal. Hari ini, ia memutuskan untuk meramalkan prestasi tim Jepang pada IOI tahun ini dengan menggunakan kartu yang bertuliskan I di sisi depan dan O di sisi belakang.

Cara meramalnya adalah sebagai berikut.

1. Pertama, tentukan bilangan bulat positif $A,B,C,D,E$.
2. Susun $A+B+C+D+E$ kartu dalam satu baris mendatar. Dari kiri, letakkan $A$ kartu dengan sisi depan menghadap ke atas, diikuti $B$ kartu dengan sisi belakang menghadap ke atas, $C$ kartu dengan sisi depan menghadap ke atas, $D$ kartu dengan sisi belakang menghadap ke atas, dan $E$ kartu dengan sisi depan menghadap ke atas. Dengan susunan ini, dari kiri terdapat $A$ buah I, $B$ buah O, $C$ buah I, $D$ buah O, lalu $E$ buah I.
3. Pilih satu atau lebih operasi dari $N$ jenis operasi yang telah ditentukan, lalu lakukan dalam urutan apa pun. Jenis operasi yang sama boleh dilakukan dua kali atau lebih. Operasi jenis $i$ ($1 \le i \le N$) adalah “membalik semua kartu dari kartu ke-$L_i$ sampai kartu ke-$R_i$, dihitung dari kiri”. Membalik satu kartu memerlukan 1 detik. Oleh karena itu, melakukan operasi jenis $i$ memerlukan $R_i-L_i+1$ detik.
4. Setelah semua operasi selesai, ramalan berhasil jika semua kartu menghadap sisi depan ke atas.

Agar tidak membalik kartu lebih banyak daripada yang diperlukan, sebelum benar-benar menggunakan kartu untuk meramal, Ketua K memutuskan untuk terlebih dahulu menentukan apakah ramalan dapat dibuat berhasil. Selain itu, jika ramalan dapat dibuat berhasil, ia ingin menentukan waktu minimum yang diperlukan untuk membuatnya berhasil.

Tugas

Diberikan informasi susunan kartu dan informasi operasi yang telah ditentukan. Buatlah program yang menentukan apakah ramalan dapat dibuat berhasil, dan jika bisa, menghitung waktu minimum yang diperlukan untuk membuatnya berhasil.

Masukan

Bacalah data berikut dari masukan standar.

• Baris pertama berisi bilangan bulat $A,B,C,D,E$ yang dipisahkan spasi. Ini berarti bahwa pada awal ramalan, dari kiri kartu disusun dengan $A$ kartu menghadap sisi depan ke atas, diikuti $B$ kartu menghadap sisi belakang ke atas, $C$ kartu menghadap sisi depan ke atas, $D$ kartu menghadap sisi belakang ke atas, dan $E$ kartu menghadap sisi depan ke atas.
• Baris kedua berisi bilangan bulat $N$. Ini menyatakan bahwa terdapat $N$ jenis operasi yang telah ditentukan.
• Baris ke-$i$ ($1 \le i \le N$) dari $N$ baris berikutnya berisi bilangan bulat $L_i,R_i$ yang dipisahkan spasi. Ini menyatakan bahwa operasi jenis $i$ adalah “membalik semua kartu dari kartu ke-$L_i$ sampai kartu ke-$R_i$, dihitung dari kiri”.

Keluaran

Jika ramalan dapat dibuat berhasil, keluarkan dalam satu baris ke keluaran standar sebuah bilangan bulat yang menyatakan waktu minimum yang diperlukan untuk membuatnya berhasil. Jika tidak, keluarkan $-1$.

Batasan

Semua data masukan memenuhi kondisi berikut.

• $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$).

Subtugas

Subtugas 1 [15 poin]

• Berlaku $N \le 10$.

Subtugas 2 [50 poin]

Kondisi berikut terpenuhi.

• $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$.

Subtugas 3 [35 poin]

Tidak ada batasan tambahan.

Contoh

Masukan 1

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

Keluaran 1

12

Penjelasan

Pada awalnya, kartu disusun sebagai IOOIIIOOOOIIIII.

Setelah melakukan operasi jenis $2$, susunannya menjadi IIIOOOOOOOIIIII. Operasi ini memerlukan 5 detik.

Selanjutnya, setelah melakukan operasi jenis $3$, susunannya menjadi IIIIIIIIIIIIIII, sehingga ramalan berhasil. Operasi ini memerlukan 7 detik.

Ramalan dapat dibuat berhasil dalam 12 detik. Karena ini adalah nilai minimum, keluarkan 12.

Masukan 2

1 1 1 1 1
1
1 1

Keluaran 2

-1

Penjelasan

Pada contoh ini ramalan tidak dapat dibuat berhasil, sehingga keluarkan $-1$.