케이크 굽기

톰의 생일이 다가오고 있고, 당신은 그의 성대한 생일 파티에 쓸 케이크를 굽는 일을 맡았습니다. 그런데 만들어야 할 케이크는 아주 많은데 시간은 매우 부족해서, 파티 전에 다 끝낼 수 있을지조차 확신할 수 없습니다!

만들어야 할 케이크 목록이 주어지며, 각 케이크는 굽는 데 정해진 시간이 걸립니다. 오븐은 정확히 3개가 있고, 각 오븐은 한 번에 케이크 하나만 구울 수 있습니다. 케이크 하나를 꺼내고 다른 하나를 넣는 데 걸리는 시간은 무시할 수 있다고 할 때, 주어진 케이크 목록을 모두 굽는 데 필요한 최소 시간을 구하세요.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 한 줄에 주어집니다. 각 줄은 정수 $n$ (단, $1 \le n \le 40$)으로 시작하며, 이는 구워야 할 케이크의 개수입니다. 그 뒤에 $n$개의 정수 $t_1, \dots, t_n$ (단, $1 \le t_i \le 30$)이 이어지며, 각각은 케이크 하나를 굽는 데 걸리는 시간(분)입니다. 입력의 끝은 정수 $0$ 하나만 있는 줄로 표시되며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다, 모든 케이크를 다 굽는 데 필요한 최소 시간(분)을 한 줄에 출력하세요.