소방서의 고민 timer 1s memory 128MB

소방차가 한 대 밖에 없는 상황에서 여러 건의 화재가 동시에 발생하였다.

한 대의 소방차를 이용하여 어떤 순서로 화재를 진압하는 것이 모든 화재를 진압하는데 걸리는 시간을 최소화할지 결정해야 한다.

다행히 다음과 같은 정보를 얻을 수 있다. 한 화재 사건에 소방차 도착이 늦으면 늦을수록 화재를 진압하는데 걸리는 시간이 같거나 길어진다. 화재의 종류에 따라서, 화재 발생 후 소방차가 t초 후에 도착하면 화재를 진압하는데 걸리는 시간은 at +b와 같이 1차 함수의 형태로 나타나게 된다. 물론 a와 b는 음수는 아니다. 화재 종류별로 a, b의 값이 일반적으로 다르게 나타나게 된다.

모든 화재 사건은 시각 0에서 발생하였다. 당신은 모든 화재를 진압하는데 걸리는 최소 시간이 얼마인지를 알고 싶다. 소방차의 이동 시간은 고려하지 않고 0으로 가정하며, 한 화재 진압이 완전히 끝나기 전에는 소방차가 다른 화재 현장으로 이동할 수 없다.