알고리즘 스터디 멤버십

알고리즘 스터디는 알고리즘 문제 풀이를 함께 공부하는 모임이다. 이 모임에는 N명이 소속되어 있고, 가입한 순서대로 0번부터 N-1번까지 번호가 매겨져 있다.

0번 회원은 멘토가 없는 유일한 회원이다. 나머지 회원은 모두 멘토를 정확히 한 명 갖는다. i번 회원의 멘토는 $S_i$번 회원이고, 0번 회원은 멘토가 없으므로 $S_0 = -1$이다. 멘토는 자신보다 먼저 모임에 들어온 사람이어야 하므로, $1 \le i \le N-1$인 모든 i에 대해 $0 \le S_i \le i-1$이다.

모임의 운영자는 회원 전원에게 알고리즘을 가르치기로 했다. 스터디는 문제 풀이에 쓰이는 알고리즘을 M개의 유형으로 나누고 1번부터 M번까지 번호를 매겨 두었다. i번 유형을 한 사람에게 가르치는 데 드는 비용은 $T_i$원이다. 회원은 각자 수업을 두 번 들어야 하며, 같은 유형의 수업을 두 번 들을 수는 없다. 교육이 끝나면 회원은 자신이 배운 두 유형에 속하는 문제는 모두 풀 수 있고, 그 두 유형에 속하지 않는 문제는 전혀 풀 수 없다.

회원은 각자 자신이 리더인 팀을 하나씩 만들어야 한다. 따라서 팀은 모두 N개 생긴다. i번 회원이 리더인 팀은 i번 회원과 멘토가 i번인 회원으로 이루어진다. 즉 $S_j = i$인 모든 j가 이 팀에 속한다. $S_k = j$이고 $S_j = i$이면, k는 i번 회원이 리더인 팀에 속하지 않는다.

어떤 팀이 프로그래밍 대회에 참가할 자격을 갖추려면 아래 조건을 만족해야 한다.

• 팀원 전원이 문제를 풀 수 있어야 한다.
• 팀원이 각자 풀 알고리즘 유형을 하나씩 정할 때, 서로 겹치지 않는 상태가 가능해야 한다.

자격 검사는 팀마다 따로 한다. 즉 한 사람이 서로 다른 팀에서 서로 다른 유형을 정해도 된다. 참가 자격을 갖춘 팀을 좋은 팀이라고 한다.

모든 팀이 좋은 팀이 되도록 각 회원에게 가르칠 두 유형을 정할 때, 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 N과 M이 주어진다. ($1 \le N \le 30$, $2 \le M \le 30$)

둘째 줄에 $S_0$부터 $S_{N-1}$까지 N개의 정수가 순서대로 주어진다. ($S_0 = -1$, $1 \le i \le N-1$인 i에 대해 $0 \le S_i \le i-1$)

셋째 줄에 $T_1$부터 $T_M$까지 M개의 정수가 순서대로 주어진다. ($1 \le T_i \le 100$)

모든 팀이 좋은 팀이 되도록 교육하는 데 필요한 비용의 최솟값을 첫째 줄에 출력한다.

모든 팀을 좋은 팀으로 만들 수 없으면 -1을 출력한다.

팀원이 k명인 팀에서는 k명이 서로 다른 유형을 정해야 한다. 그러므로 그 팀원이 배운 유형을 모두 모으면 서로 다른 유형이 k개 이상이어야 하고, 나아가 팀원마다 유형을 하나씩 겹치지 않게 나누어 가질 수 있어야 한다.

회원이 한 명뿐인 팀은 항상 좋은 팀이다. 모임에 회원이 한 명뿐이면 가장 싼 두 유형을 가르치는 것이 비용이 가장 적다.