PR- 키위 주스 > 문제은행 : 정보올림피아드&알고리즘

2356 : 키위 주스

제한시간
2000 ms   
메모리제한
128 MB   
해결횟수
31 회   
시도횟수
81 회   

문제

0부터 N - 1까지 번호가 차례로 매겨진 눈금 없는 병이 있다. 각 병의 용량은 C 리터로 모두 같다.

 

이 병들에 각각 병에 Bi 리터씩의 키위 주스를 담았다. 

이 키위 주스들을 판매하려고 하는데, 그 전에 주스들을 서로 옮겨 담을 수 있다. 

즉, 서로 다른 두 병 A와 B를 골라 A 병에서 B 병으로 주스를 옮겨 담아 A가 비거나 B가 가득찰 때까지 옮기는 것이다. 

이렇게 옮겨 담은 병의 가치는 x리터가 담긴 병에 대해 Px 달러이다. 모든 병의 가치의 총 합을 최대화하라.


입력형식

입력은 세 줄로 구성된다. 첫 줄에는 C와 N이 공백으로 구분되어 주어진다. 

다음 줄에는 각 N개의 병에 병에 담긴 주스의 양인 Bi가 공백으로 구분되어 주어진다. 

마지막 줄에는 병에 담긴 용량에 따른 가치인 Pi 가 i가 0일때부터 C일때까지 순서대로 공백으로 구분되어 주어진다. (0부터 C까지는 총 C+1개의 수가 있다.)

 

입력 예를 참고하라.

 

제약 조건 

- C 는 1 이상 49 이하의 정수이다. 

- N 은 1 이상 15 이하의 정수이다. 

- Bi 는 0 이상 C 이하의 정수이다. 

- Pi 는 0 이상 106 이하의 정수이다.


출력형식

입력에 대한 최대 가치를 구하여 하나의 행에 출력한다.


입력 예

10 2
5 8
0 0 0 0 0 0 0 0 0 0 10

출력 예

10

입력 예

10 2
5 8
0 0 0 0 0 10 10 10 10 10 10

출력 예

20

입력 예

10 4
4 5 3 7
14 76 12 35 6 94 26 3 93 90 420

출력 예

625

입력 예

1 1
0
1000000 1000000

출력 예

1000000

출처

PR

경기도 안양시 동안구 평촌대로 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