34334번 - 화단 꾸미기

문제

화단에 $N$개의 꽃들이 차례대로 심겨 있다. $i$번 꽃은 아름다움 $A_i$를 가지고 있다.

당신은 화단을 더욱 예쁘게 꾸미기 위하여 $M$개의 종류의 장식을 $K$개씩 가지고 왔다.

$i$번 장식을 꽃에 달면 아름다움이 $B_i$배가 된다.

장식 사용 규칙은 다음과 같다.

• 한 꽃에는 장식을 최대 하나까지 달 수 있다.
• 같은 장식을 단 꽃들은 반드시 연속되어야 한다.
• 한 장식을 $K$개 초과하여 사용할 수 없다.

목표는 장식들을 적절히 배치하여, 화단 전체 꽃들의 아름다움 총합을 최대로 만드는 것이다.

입력

첫째 줄에 세 정수 $N, M, K$가 공백으로 구분되어 주어진다. $(1 \le N \le 100; 1 \le M \le 10; 1 \le K \le N)$

둘째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^6)$

셋째 줄에 $M$개의 정수 $B_1, B_2, \cdots, B_M$이 공백으로 구분되어 주어진다. $(1 \le B_i \le 10^6)$

출력

가능한 장식 배치 중 꽃들의 아름다움 총합의 최댓값을 출력한다.

제한

힌트