키위주스

최대 용량이 $C$리터인 병이 $N$개 있다. $i$번 병에는 키위주스가 $B_i$리터 들어 있다.

도토리는 이 키위주스를 팔아 노트북을 새로 사려고 한다. 주스 한 병의 값은 그 병에 들어 있는 양으로만 정해진다. 0리터부터 $C$리터까지 양마다 값이 따로 매겨져 있고, 많이 들어 있다고 해서 값이 더 비싸지는 않다. 0리터가 든 병 하나가 $C$리터로 가득 찬 병 하나보다 비쌀 수도 있다.

도토리는 병을 그대로 팔지 않고 주스를 서로 옮겨 담아 값을 더 올리려고 한다. 옮겨 담는 규칙은 이렇다. 서로 다른 두 병 $A$와 $B$를 골라 $A$에서 $B$로 주스를 옮기면, $A$가 비거나 $B$가 가득 찰 때까지 멈추지 않고 부어야 한다. 예를 들어 $C = 10$이고 $A$에 5리터, $B$에 7리터가 들어 있으면 옮긴 뒤 $A$는 3리터, $B$는 10리터가 된다. 같은 조건에서 $A$가 3리터, $B$가 4리터였다면 옮긴 뒤 $A$는 0리터, $B$는 7리터가 된다.

옮겨 담는 횟수에는 제한이 없다. 도토리는 주스가 모두 팔린다고 확신하므로 병 $N$개의 값을 전부 더한 금액을 받는다. 도토리가 받을 수 있는 금액의 최댓값을 구하여라.

첫째 줄에 병의 개수 $N$과 병의 최대 용량 $C$가 주어진다. ($1 \le N \le 15$, $1 \le C \le 49$)

둘째 줄에 각 병에 들어 있는 주스의 양 $B_1, B_2, \dots, B_N$이 주어진다. ($0 \le B_i \le C$)

셋째 줄에 양마다의 값 $P_0, P_1, \dots, P_C$가 0리터부터 $C$리터까지 차례로 주어진다. ($0 \le P_i \le 10^6$)

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