문제
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 이하의 정수이다.
출력
입력에 대한 최대 가치를 구하여 하나의 행에 출력한다.
예제 #1
10 2
5 8
0 0 0 0 0 0 0 0 0 0 10
10
예제 #2
10 2
5 8
0 0 0 0 0 10 10 10 10 10 10
20
예제 #3
10 4
4 5 3 7
14 76 12 35 6 94 26 3 93 90 420
625
예제 #4
1 1
0
1000000 1000000
1000000
태그
출처
PR
로그인해야 코드를 작성할 수 있어요.