27212번 - 미팅

문제

오늘은 A대학의 학생 $N$명과 B대학의 학생 $M$명이 만나는 날이다. 이들이 만나는 장소에는 크고 길이가 긴 식탁이 하나 있어서, 한쪽에는 A대학 학생이, 다른 한쪽에는 B대학 학생이 앉을 예정이다. A대학 학생은 1ドル$부터 $N$까지, B대학 학생들은 1ドル$부터 $M$까지 번호가 붙어 있다. 의자에 앉을 때는 번호가 증가하는 순서대로 앉는다.

모든 일정이 끝나면 학생들은 서로 악수를 한다. 한 사람은 최대 한 사람과 악수를 할 수 있다. 이때, 팔이 교차하면 악수를 할 때 불편하기 때문에, 팔이 교차하지 않게 악수를 해야 한다. 악수를 하지 못하는 사람이 생길 수도 있다. 즉, 총 $K$쌍이 생긴 상황에서, 어떤 $i,ドル $j$ (1ドル \leq i < j \leq K$)에 대해, $i$번째 쌍이 A대학의 $x_i$번째, B대학의 $y_i$번째 학생이 악수를 했고, $j$번째 쌍이 A대학의 $x_j$번째, B대학의 $y_j$번째 학생이 악수를 했고 하면 $x_i < x_j$이면 $y_i < y_j$여야 한다.

학생의 성격을 1ドル$ 이상, $C$ 이하의 정수로 나타낼 수 있다. 성격이 $a$인 사람과 $b$인 사람이 악수를 할 경우, $W[a][b]$만큼의 만족도를 얻는다고 한다. 모든 학생들의 성격을 알고 있을 때, 가능한 만족도의 합의 최댓값을 구하고 싶다. 이를 구하는 프로그램을 작성하라.

입력

첫째 줄에는 $N,ドル $M,ドル $C$가 공백을 사이에 두고 주어진다.

둘째 줄부터 $C+1$번째 줄에서, $i+1$번째 줄에는 $W[i][1], W[i][2], \dots, W[i][C]$의 값이 순서대로 공백을 사이에 두고 주어진다.

$C+2$번째 줄에는 A대학 학생 $N$명의 성격 정보를 나타내는 $N$개의 정수가 공백을 사이에 두고 순서대로 주어진다.

$C+3$번째 줄에는 B대학 학생 $M$명의 성격 정보를 나타내는 $M$개의 정수가 공백을 사이에 두고 순서대로 주어진다.

출력

미팅의 만족도의 합으로 가능한 최댓값을 1개의 줄에 걸쳐서 출력한다.

제한

• 1ドル\leq N \leq 1000$
• 1ドル\leq M \leq 1000$
• 2ドル\leq C \leq 16$
• 1ドル\leq A_i \leq C$ (1ドル \leq i \leq N$)
• 1ドル\leq B_i \leq C$ (1ドル \leq i \leq M$)
• 1ドル\leq W[i][j] \leq 1000000000$ (1ドル \leq i, j \leq C$)
• $W[i][j] = W[j][i]$ (1ドル \leq i, j \leq C$)

힌트