최근 서울 지하철 9호선이 3기 지하철 (9,10,11호선) 중 살아남아 유일하게 개통되 었다. 그런데 서울 지하철 9호선 운영 주식 회사는 문제가 생겼다.
서울메트로나 5678도 시철도나 코레일처럼 청소 구간과 청소 비용 이 일정한 철도 정리 열차를 가지고 있지 않 다. 따라서 수입을 해야하는데, 한 회사에 물 량이 정해져 있지 않아 여러 회사에서 구매 를 해야한다.
여러회사에서도 성능이 각각 다르다. 어떤 회사는 2개의 구간만 청소 가능한 것도 있 고, 비용이 다른 회사보다 비싼 것도 있다.
서울 지하철 9호선 운영 주식회사에 근무하 고 있는 신란이는 최소의 비용으로 모든 구 간을 커버하면서 최소비용을 구하는 프로그 램을 작성하시오.
단, 각각의 열차가 담당하는 구간의 합은 전 체구간의 길이와 같아야 한다. 즉 비용이 더 저렴하지만 모든 담당구간의 길이보다 더 길 면 열차 담당구간이 겹치게 되어 결국은 돈 이 더 들기 때문이다. 프로그램의 실행시간은 2초를 넘을 수 없다. 부분점수는 없다.
입력 5 3 1 1 1 1 1 1 1 1 3 출력 5 입력 5 3 1 1 1 1 1 1 1 1 1 출력 -1
출처:conankun