시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 12 2 2 66.667%

문제

최대용량이 C리터인 병이 N개 있다. 각 병에는 Bi리터만큼의 키위쥬스가 담겨 있다. 도토리는 이 키위쥬스를 팔아 노트북을 바꾸려고 한다. 키위쥬스의 가격은 그 병에 얼만큼의 키위쥬스가 담겨있는지로 결정된다. 0리터부터 C리터까지 가격이 매겨져 있는 것이다. 도토리의 장사수완은 평범한 사람이 이해하기 힘들기 때문에 들어있는 용량이 많다고 해서 더 높은 가격을 책정하지는 않는다. 0리터가 든 키위쥬스 1병이 C리터로 꽉 찬 키위쥬스 1병보다 비쌀 수도 있는 것이다.

도토리는 키위쥬스 병들을 이대로 팔지 않고 서로 옮겨 담아 더 많은 이익을 내고싶다. 쥬스를 옮겨담을 때에는 규칙이 있다. 서로 다른 두 병 A와 B를 골라 A병에서 B병으로 쥬스를 옮겨담으려면 A가 비거나 B가 가득찰 때까지 옮겨야한다. 즉 최대용량 C가 10리터고 A에 들어있는 쥬스가 5리터, B에 들어있는 쥬스가 7리터라면 A를 B에 옮겨담은 후에는 A가 3리터, B가 10리터가 된다. 같은 조건에서 A가 3리터, B가 4리터라면 A를 B에 옮겨담은 후에는 A가 0리터, B가 7리터가 된다.

도토리는 키위쥬스가 모두 팔릴거라 확신하므로, 각 키위쥬스의 가치 합이 최대가 되도록 이 키위쥬스들을 옮겨담으려고 한다. 도토리가 키위쥬스를 팔아 얻을 수 있는 금액의 합의 최대는 얼마인지 알아보자,

입력

첫 줄에 병의 개수 N(1 ≤ N ≤ 15), 병의 최대용량 C(1 ≤ C ≤ 49)가 주어진다. 두 번째 줄에는 N개의 병에 담긴 키위쥬스의 현재 용량 Bi(0 ≤ Bi ≤ C)가 주어진다. 세 번째 줄에는 (C + 1)개의 각 용량마다의 가격 Pi(0 ≤ Pi ≤ 1000000)가 주어진다. Pi가 주어지는 순서는 0리터부터 C리터까지 순차적이다.

출력

한 줄에 도토리가 얻을 수 있는 금액의 최댓값을 출력한다.

예제 입력 1

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

예제 출력 1

10

예제 입력 2

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

예제 출력 2

20

예제 입력 3

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

예제 출력 3

625

예제 입력 4

1 1
0
1000000 1000000

예제 출력 4

1000000