문제
예능 프로그램인 “런닝맨” 에서, 두 스파이 일우와 민호는 스파이가 아닌 N명의 다른 멤버들을 아웃시키려고 한다.
일우와 민호가 각자 따로따로 행동해도 멤버들을 아웃시킬 수 있지만, 어쩔 때는 둘이 협동해서 아웃시키는 것이 훨씬 이득이 되는 경우가 있다. 이 땐 일우와 민호가 만나서 아웃시킬 멤버를 정하고 같이 그 멤버를 아웃시키러 간다.
아웃시킬 목표물이 k번째 멤버일 때 일우가 그 멤버를 아웃시키기로 계획하고 아웃시키기까지는 Jk 분이 걸리고, 민호가 그 멤버를 아웃시키기로 계획하고 아웃시키기까지는 Lk 분이 걸린다. 이 둘이 협동해서 그 멤버를 아웃시키기까지는 Ck 분이 걸린다. 일우와 민호는 근성이 매우 강하기 때문에, 목표물 한 명을 정하면 그 목표물을 아웃시키기 전까지는 다른 목표물을 정하지 않는다. 어쩔 때는 목표물을 설정하지 않을 수도 있다.
멤버들을 빨리 아웃시키지 않으면, 멤버들이 일우와 민호가 스파이라는 것을 알 수 있기 때문에 이 둘은 최대한 빨리 N명을 아웃시키려고 한다.
일우와 민호를 도와서 N명의 멤버들을 아웃시킬 수 있는 최소 시간(분)을 구하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 N (1≤N≤30) 이 입력된다.
두 번째 줄부터 N개의 줄에서는 Jk, Lk, Ck (1≤Jk Lk Ck≤30)가 입력된다.
출력
최소 시간(분)을 출력한다.
예제
3
23 25 9
10 14 11
16 13 12
22
0분 : 일우는 2번 멤버를 아웃시키러 가고, 민호는 3번 멤버를 아웃시키러 간다.
10분 : 일우가 2번 멤버를 아웃시키고, 목표를 설정하지 않는다.
13분 : 민호가 3번 멤버를 아웃시키고, 이 둘이 같이 1번 멤버를 아웃시키러 간다.
22분 : 일우와 민호가 1번 멤버를 아웃시킨다.
로그인해야 코드를 작성할 수 있어요.