톰의 생일이 다가오고 있다. 당신은 그의 크고 아름다운 파티를 위해 케이크를 만들어야 하지만, 만들어야 할 케이크는 많고 시간은 없다. 그래서 당신은 파티 전에 다 만들 수 있을지 장담할 수 없다!
당신은 만들어야 할 다양한 케이크와 걸리는 시간을 알고 있고, 또한 3개의 오븐이 있다. (단, 한 개의 오븐에 여러 개의 케이크를 동시에 넣을 수 없으며, 케이크를 오븐에서 꺼내는 시간은 무시한다) 케이크를 만드는 데 필요한 최소한의 시간을 구해야 한다.
만들어야 할 케이크 수 N(1 ≤ N ≤ 40)과 N개의 케이크를 만드는 데 걸리는 시간 tn(1 ≤ ti ≤ 30)이 입력된다.
입력 1 30 3 15 10 20 5 6 7 8 9 10 0 출력 30 20 15
출처:Stanford local 2007 번역:abc