화단 꾸미기

화단에 $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)$

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