13393번 - 스타트링크 알고리즘 멤버십

스타트링크 알고리즘 멤버십(SAM)은 알고리즘 문제 풀이를 주로 공부하는 모임이다. 이 모임에는 총 N명의 사람들이 소속되어 있고, 가입한 순서대로 0번부터 N-1번까지 번호가 매겨져 있다.

0번 회원은 SAM에서 멘토가 없는 유일한 회원이다. 나머지 모든 회원은 정확하게 한 명의 멘토를 갖는다. i번 회원의 멘토는 S_i로 나타내며, 0번 회원은 멘토가 없기 때문에, S₀은 -1이다.

각 회원의 멘토는 자신보다 먼저 SAM에 들어온 사람이어야 한다. 따라서, 모든 i(1 ≤ i ≤ N-1)번 회원의 멘토 S_i는 0보다 크거나 같고, i-1보다 작거나 같아야 한다.

어느 날, 알 수 없는 사건이 발생해서 SAM의 모든 회원이 아무 문제도 풀 수 없는 상황이 되어버렸다. SAM을 운영하는 백준(회원은 아님)이는 회원들에게 알고리즘을 교육시키기로 결정했다.

SAM에서는 알고리즘 문제 풀이에 사용되는 알고리즘을 M개의 유형으로 분류해 놓았고, 1번부터 M번까지 번호를 매겨놓았다. 어떤 사람에게 i번 유형에 해당하는 알고리즘을 교육하는데 필요한 비용은 T_i원이다. 모든 회원은 수업을 각자 2번씩 들어어야 하며, 같은 유형의 알고리즘 수업을 두 번 들을 수는 없다. 교육이 끝난 후에 모든 회원은 자신이 배운 두 가지 알고리즘 유형에 해당하는 문제는 모두 풀 수 있고, 그 유형에 속하지 않는 문제는 전혀 풀 수 없다.

SAM의 각 회원은 자신을 리더로하는 팀을 하나씩 만들어야 한다. 즉, SAM에는 총 N개의 팀이 생기게 된다. i번 사람을 리더로하는 팀은 i번 사람과, i번 사람이 멘토인 회원으로 이루어져 있다. 즉, S_j = i인 모든 j가 i를 리더로하는 팀에 속해있게 되는 것이다. 만약, S_k = j이고, S_j = i인 경우에 k는 i를 리더로하는 팀에 소속되어 있지 않다.

오늘은 각 팀이 프로그래밍 대회에 참가할 자격이 있는지 알아보려고 한다. 프로그래밍 대회에 참가할 자격이 있는 팀은 아래와 같은 조건을 만족해야 한다.

• 모든 팀원이 문제를 풀 수 있어야 한다.
• 각 팀원이 자신이 풀 알고리즘 문제 유형을 하나씩 결정했을 때, 겹치는 것이 없는 상태가 가능해야 한다.

각 팀마다 프로그래밍 대회에 참가할 자격이 있는지 알아보는 것이기 때문에, 각각의 팀마다 따로 따로 참가할 자격이 있는지 검사를 해보면된다. 즉, 각 사람이 서로 다른 팀에서 다른 알고리즘 유형을 결정해도 된다. 만약 프로그래밍 대회에 참가할 자격이 있다면, 그 팀을 좋은 팀이라고 한다.

이제, 모든 팀이 좋은 팀이 되게 하기 위해서, 백준이는 각 사람에게 어떤 두 유형을 가르쳐야하는지 결정해야 한다. 이때, 필요한 비용을 최소로 하는 프로그램을 작성하시오.

첫째 줄에 N, M (1 ≤ N ≤ 30, 2 ≤ M ≤ 30)이 주어지고, 둘째 줄에는 S_i가 S₀부터 순서대로, 셋째 줄에는 T_i가 T₁부터 순서대로 주어진다. (0 ≤ S_i ≤ i-1, S₀ = -1, 1 ≤ T_i ≤ 100)

첫째 줄에 모든 팀이 프로그래밍 대회에 참가할 수 있게 교육하기 위한 비용의 최솟값을 출력한다.

만약, 모든 팀이 프로그래밍 대회에 참가할 수 없으면 -1을 출력한다.

예제 1의 경우에 한 명 밖에 없다. 0번 회원에게 1, 2번 알고리즘을 가르치면 비용은 1+2 = 3이 된다.

예제 2의 경우는 다음과 같이 교육을 하면 된다.

• 0번 회원이 1번과 2번 알고리즘을 배운다. 비용 1+2 = 3.
• 1번 회원이 1번과 2번 알고리즘을 배운다. 비용 1+2 = 3.
• 2번 회원이 1번과 3번 알고리즘을 배운다. 비용 1+3 = 4.

이렇게 되어버리면 모든 팀은 프로그래밍 대회에 참가할 수 있다.

• 0번 회원을 리더로 하는 팀은 0, 1, 2번 회원으로 이루어져 있다. 1, 2, 3번 유형을 풀기로 결정하며 ㄴ된다.
• 1번 회원을 리더로 하는 팀은 1번 회원 혼자로 이루어져 있기 때문에 참가할 수 있다.
• 2번 회원을 리더로 하는 팀도 혼자이기 때문에 참가할 수 있다.