이야기 배열

도깨비 나라에 사는 도깨비 깨비는 오늘도 세상에서 가장 재미있는 이야기 배열을 만들기 위해 고민 중이다. 이야기 배열은 $N$개의 순서를 가진 이야기들로 이루어진다.

이야기는 각각 재미 값과 길이 값을 가지고 있으며 이야기 배열의 재미는 배열을 이루는 모든 이야기의 재미의 총합으로 정의된다.

현재 깨비에게는 $A$, $B$, $C$ 세 개의 이야기보따리가 있고, 각 보따리는 $N$개의 서로 다른 이야기를 가지고 있다.

깨비는 세 개의 보따리에서 총 $N$개의 이야기를 뽑아 가장 재미있는 이야기 배열을 만들고자 한다. 보따리에서 뽑은 이야기는 단 한 번만 사용할 수 있음에 유의하자.

단, 이야기 배열에서 인접한 이야기가 같은 보따리에서 나왔다면 배열이 식상해지므로 인접한 이야기는 서로 다른 보따리에서 뽑아야 한다. $1 \le i < N$인 $i$에 대해 $i$번 이야기와 $i+1$번 이야기는 서로 인접한다.

또한 처음부터 이야기의 길이가 길어도 배열이 지루해지므로 이야기 배열의 $i$번째 이야기는 정해진 길이 $D\_{i}$보다 커서는 안 된다.

이야기 배열의 정해진 길이 상한값은 단조 증가 하는 형태이다. 즉, $1 \le i < N$에 대해 $D\_{i} \le D\_{i+1}$를 항상 만족한다.

주어진 조건을 만족하면서 깨비가 만들 수 있는 배열 중 재미 값이 최대가 되는 배열의 재미를 출력하자.

입력의 첫 줄에 이야기 배열의 길이와 각 보따리의 크기를 나타내는 정수 $N$이 주어진다. ($1$ $\le$ $N$ $\le$ $50$)

다음 입력의 $N$개 줄에 걸쳐 $A$ 보따리를 구성하는 이야기들의 정보가 각 줄마다 $A\_{F\_{i}}$ $A\_{L\_{i}}$의 정수 형태로 주어진다. $A\_{F{i}}$ 는 $A$ 보따리를 구성하는 $i$번 이야기의 재미 $A\_{L{i}}$는 $i$번 이야기의 길이다. ($1$ $\le$ $A\_{F{i}}$ $\le$ $5000$ , $1$ $\le$ $A\_{L{i}}$ $\le$ $5000$)

다음 입력의 $N$개 줄에 걸쳐 $B$ 보따리를 구성하는 이야기들의 정보가 각 줄마다 $B\_{F\_{i}}$ $B\_{L\_{i}}$의 정수 형태로 주어진다. $B\_{F{i}}$ 는 $B$ 보따리를 구성하는 $i$번 이야기의 재미 $B\_{L{i}}$는 $i$번 이야기의 길이다. ($1$ $\le$ $B\_{F{i}}$ $\le$ $5000$ , $1$ $\le$ $B\_{L{i}}$ $\le$ $5000$)

다음 입력의 $N$개 줄에 걸쳐 $C$ 보따리를 구성하는 이야기들의 정보가 각 줄마다 $C\_{F\_{i}}$ $C\_{L\_{i}}$의 정수 형태로 주어진다. $C\_{F{i}}$ 는 $C$ 보따리를 구성하는 $i$번 이야기의 재미 $C\_{L{i}}$는 $i$번 이야기의 길이다. ($1$ $\le$ $C\_{F{i}}$ $\le$ $5000$ , $1$ $\le$ $C\_{L{i}}$ $\le$ $5000$)

입력의 마지막 줄에 이야기 배열을 구성하는 $i$번째 이야기의 길이 상한을 나타내는 배열이 $D\_{1}$ .. $D\_{N}$ 의 정수 형태로 주어진다. ($1$ $\le$ $D\_{i}$ $\le$ $5000$)

주어진 조건을 만족하면서 깨비가 만들 수 있는 가장 재미있는 이야기 배열의 재미 값을 출력하자.

만약 주어진 조건 내에서 아무런 이야기 배열도 만들 수 없다면 $-1$을 출력하자.