IOIOI 카드

시간 제한1초메모리 제한512 MB

요약

I/O 카드가 일렬로 놓여 있고 구간 뒤집기 연산마다 비용이 다를 때, 모든 카드를 앞면으로 만들 수 있는지 판정하고 최소 뒤집기 시간을 구한다.

문제

K 이사장은 점술을 좋아해서 늘 여러 가지 점을 친다. 오늘은 앞면에 'I', 뒷면에 'O'가 적힌 카드를 사용해 올해 IOI에서 일본 선수단이 거둘 성적을 점치기로 했다.

점을 치는 방법은 다음과 같다.

먼저 양의 정수 $A, B, C, D, E$ 를 정한다.
$A + B + C + D + E$ 장의 카드를 가로로 한 줄로 늘어놓는다. 이때 왼쪽에서 $A$ 장은 앞면, 이어서 $B$ 장은 뒷면, 이어서 $C$ 장은 앞면, 이어서 $D$ 장은 뒷면, 이어서 $E$ 장은 앞면이 되도록 늘어놓는다. 이렇게 늘어놓으면 왼쪽부터 차례대로 'I'가 $A$ 개, 'O'가 $B$ 개, 'I'가 $C$ 개, 'O'가 $D$ 개, 'I'가 $E$ 개 놓이게 된다.
미리 정해진 $N$ 종류의 조작 가운데 1개 이상을 골라 원하는 순서로 행한다. 이때 같은 종류의 조작을 2번 이상 행해도 된다. $i$ ( $1 \le i \le N$ )번째 종류의 조작은 "왼쪽에서 $L_i$ 번째부터 $R_i$ 번째까지의 카드 앞뒤를 모두 뒤집는다"는 것이다. 카드 한 장을 뒤집는 데 1초가 걸린다. 따라서 $i$ 번째 종류의 조작을 행하는 데는 $R_i - L_i + 1$ 초가 걸린다.
조작이 끝난 뒤 모든 카드가 앞면이면 점은 성공이다.

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$ 을 출력하라.