돌 장인

당신은 석기 시대의 이름난 장인이었고, 자연석을 깎아 온갖 도구를 만드는 데 평생을 바쳤다. 그 작품은 2006년의 박물관에도 정중히 전시되어 있다. 하지만 박물관을 찾는 사람은 대부분 그 앞에 오래 머물지 않는다. 하늘에서 그 모습을 내려다보다가, 당신은 미친 듯이 일하던 그 시절을 떠올렸다.

가장 바빴던 어느 날, 당신은 도구 주문을 여러 건 받았다. 주문마다 서로 다른 도구 하나를 요청했다. 맨돌만 가지고 주문 하나를 채우려면 며칠이 걸리기도 했다. 그러나 이미 완성해 둔 도구가 있으면 새 도구를 더 빨리 깎을 수 있었다. 주문 목록의 도구마다 그 도구를 깎는 데 도움이 되는 도구가 정확히 하나씩 정해져 있다.

도구 하나를 깎는 데 걸리는 날수는 두 가지다. 보조 도구 없이 맨돌부터 깎으면 $day_1$일이 걸리고, 깎기 시작하는 시점에 보조 도구가 이미 완성되어 있으면 $day_2$일만 걸린다. 보조 도구가 자기 자신으로 지정된 도구도 있는데, 그 도구는 자기 자신의 도움을 받을 수 없다.

도구는 한 번에 하나씩만 깎으므로, 전체 기간은 도구별 날수의 합이다. 모든 주문을 채우는 데 걸리는 최소 날수를 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 주문된 도구의 개수 $N$이 주어진다.

이어지는 $N$개의 줄에는 주문 하나가 네 개의 값으로 주어지며, 값 사이는 한 개 이상의 공백으로 구분된다. 순서는 $name$, $day_1$, $sup$, $day_2$이다. $name$은 해당 주문의 도구 이름이고, $day_1$은 보조 도구 없이 그 도구를 만드는 데 필요한 날수이며, $sup$은 그 도구를 깎는 데 도움이 되는 도구의 이름이고, $day_2$는 $sup$을 먼저 완성한 뒤 그 도구를 만드는 데 필요한 날수다.

입력은 $N = 0$인 줄로 끝난다. 이 줄은 처리하지 않는다.

• $N \le 1000$
• $name$은 공백이 없는 32자 이하의 문자열이고, 같은 테스트 케이스 안에서 서로 다르다
• $sup$은 같은 테스트 케이스에 주어진 이름 중 하나이며, $name$ 자신일 수도 있다
• $0 < day_2 < day_1 < 20000$

각 테스트 케이스마다 $N$개의 주문을 모두 채우는 데 필요한 최소 날수를 한 줄에 출력한다.