24529번 - 이야기 배열

문제

도깨비 나라에 사는 도깨비 깨비는 오늘도 세상에서 가장 재미있는 이야기 배열을 만들기 위해 고민 중이다. 이야기 배열은 $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$을 출력하자.

제한

힌트