문제
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
입력
102
58
000000000010
출력
10
예제2
입력
102
58
00000101010101010
출력
20
예제3
입력
104
4537
147612356942639390420
출력
625
예제4
입력
11
0
10000001000000
출력
1000000
출처
PR