31929번 - 너 재능 있어

문제

리그 오브 레전드(이하 롤)를 즐기는 민우는 자기보다 롤을 못하는 민석이를 도발했다.

너? 재능 있어. 열심히 해.

민석이는 너무 분하여 어떻게 하면 점수를 효율적으로 올릴 수 있는지 연구하기 시작했다. 철저한 자기 객관화가 가능한 민석이는 앞으로의 게임에서 $N$번의 승리와 $M$번의 패배를 하게 될 것이란 사실을 알고 있다. 민석이는 $i$번째 승리를 하게 된다면 $W_{i}$만큼의 점수를 얻게 되고, $j$번째 패배를 하게 된다면 $L_{j}$만큼의 점수를 잃게 된다. 민석이의 점수는 0ドル$점에서 시작하고, 점수는 음수가 될 수 있다.

롤에는 민석이와 같은 하수들이 한 번에 너무 큰 점수를 잃지 않도록 매 $K$점마다 점수 보호권이 존재한다. 정수 $a$와 0ドル< b < K$를 만족하는 정수 $b$에 대하여, 민석이의 현재 점수가 $a\times K+b$라고 하자. 만약 민석이가 이 상태에서 $j$번째 패배를 당했다면, 현재 점수에서 $b$점을 초과하여 잃지 않는다. 다시 말해, 민석이는 $\min(L_{j},b)$만큼의 점수를 잃게 된다. 만약 현재 점수가 $a\times K$라면, $L_{j}$만큼의 점수를 잃게 됨에 유의하자.

당연하게도 민석이는 $N+M$번의 게임 후 가장 높은 점수를 얻고 싶다. 민석이를 도와주자.

입력

첫 번째 줄에 승리 시 얻을 수 있는 점수를 나타내는 배열 $W$의 길이 $N$이 주어진다. $(1\leq N \leq 1,000円)$

두 번째 줄에 $W$의 원소 $N$개가 공백으로 구분되어 주어진다. $W$의 모든 원소는 1ドル$ 이상 100ドル$ 이하의 정수다.

세 번째 줄에 패배 시 잃게 되는 점수를 나타내는 배열 $L$의 길이 $M$이 주어진다. $(1\leq M \leq 1,000円)$

네 번째 줄에 $L$의 원소 $M$개가 공백으로 구분되어 주어진다. $L$의 모든 원소는 1ドル$ 이상 100ドル$ 이하의 정수다.

다섯 번째 줄에 점수 보호를 위한 정수 $K$가 주어진다. $(100\leq K \leq 1,000円)$

출력

$N$번의 승리와 $M$번의 패배를 한 후 민석이가 얻을 수 있는 점수의 최댓값을 출력한다.

제한

힌트