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

설명 1

처음에 카드는 IOOIIIOOOOIIIII로 배열되어 있습니다. 2번째 작업을 수행하면 IIIOOOOOOOIIIII가 됩니다. 이 작업은 5초가 걸립니다. 그 후 3번째 작업을 수행하면 IIIIIIIIIIIIIII가 되어 점술이 성공합니다. 이 작업은 7초가 걸립니다. 점술은 12초 만에 성공시킬 수 있습니다. 이것이 최솟값이므로 12를 출력합니다.

입력 2

1 1 1 1 1
1
1 1

출력 2

-1

설명 2

이 입력 예제에서는 점술을 성공시킬 수 없으므로 -1을 출력합니다.