USACO 2013 November Gold No Change- 여객선 (Cruise) > 문제은행 : 정보올림피아드&알고리즘




2720 : 여객선 (Cruise)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
75 회   
시도횟수
677 회   

문제

정올시 항구에서, N명의 승객들이 줄을 서서 KOI 섬으로 가는 배를 기다리고 있다.



한편, 출항을 할 수 있는 배의 수는 B척밖에 없고, 각 선박마다 안전을 위해 최대수용무게를 정해놓았기 때문에 출항 순서를 잘 정해야 한다. 선박 한 대가 출항을 위해 잠시 항구에 정박해 있으면, 승객들은 앞에서부터 순서대로 몇 명씩 배에 타게 된다. 이 때, 배에 타는 승객들의 몸무게의 합은 최대수용무게를 넘어서는 안 되며, 줄을 이탈하거나 새치기하는 승객들은 없다.



배가 출항을 하게 되면 연료를 소모하게 되는데, 연료 소모량이 최대수용무게와 비례한다. 따라서 항구 측에서는 출항하지 않는 배들의 최대수용무게의 합을 최대화해야 한다.



배의 정보와 승객들의 몸무게의 정보가 주어질 때 출항하지 않는 배들의 최대수용무게의 합을 최대화하는 프로그램을 작성하여라.


입력형식

첫 번째 줄에는 배의 수 B와 승객의 수 N이 주어진다. (1 ≤ B ≤ 16, 1 ≤ N ≤ 100,000) 두 번째 줄부터 B개의 줄에는 각 배의 최대수용무게가 주어진다. 최대수용무게는 100,000,000 이하의 자연수이다. 그 다음 줄부터 N개의 줄에는 각 승객의 몸무게가 줄 선 순서대로 주어진다. 몸무게는 10,000 이하의 자연수이다. 전체 데이터의 40%는 B ≤ 10 이고 N ≤ 5,000을 만족한다.

출력형식

출항하지 않는 배들의 수용무게의 합의 최댓값을 출력한다. 만약 모든 배를 출항해도 승객들을 모두 태울 수 없다면 -1을 출력한다.

입력 예

3 6
12
15
10
6
3
3
2
3
7

출력 예

12

Hint!

최대 수용무게가 10인 배를 이용해서 1, 2번째 승객을 태운 다음, 최대 수용무게가 15인 배를 이용해서 3, 4, 5, 6번째 승객을 태우면 최대 수용무게가 12인 배를 출항하지 않으므로 최적이 된다.



경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP