3+1 아이스크림 timer 1s memory 32MB

안양마트에서는 다음과 같은 아이스크림 할인 이벤트를 실시하고 있다.

서로 다른 종류의 아이스크림 4개를 사면 그중 가격이 높은 3개의 금액만 계산하고 가장 가격이 낮은 한 개의 아이스크림은 공짜로 주는 것이다. 철이는 마트에 있는 모든 종류의 아이스크림을 한 개씩 사고 싶어졌다.

모든 아이스크림의 가격을 확인하고는 4개씩 묶어서 지불해야 하는 금액을 계산하려고 보니 묶는 방법에 따라 그 금액이 달라지는 것을 확인한 철이는 어떻게 하면 가장 적은 돈으로 모든 아이스크림을 살 수 있는지 생각해 보기로 했다.

예를 들어 마트에는 9종류의 아이스크림이 있고 각각의 가격이 500, 400, 700, 300, 600, 900, 350, 200, 750원이라면 (500, 400, 700, 300), (600, 900, 350, 200), (750) 이렇게 묶게 되면 300원과 200원 두 개를 서비스로 받게 되므로 지불해야 하는 금액은 4200원이지만 (700, 600, 900, 750), (500, 400, 300, 350), (200) 이렇게 묶게 되면 600원과 300원 두 개를 서비스로 받게 되어 3800원만 내면 된다.

철이를 도와 모든 종류의 아이스크림을 사기 위한 최소 비용을 구하는 프로그램을 작성해 주자.