캐릭터 훈련

해빈이는 여러 캐릭터를 가지고 있으며, 각 캐릭터의 레벨은 1 이상 N 이하의 정수이다. 앞으로 D일 동안 캐릭터를 훈련해서 모든 캐릭터의 힘의 합을 최대화하려고 한다.

하루에는 캐릭터 하나를 골라 훈련할 수 있다. 레벨이 N보다 낮은 캐릭터를 하루 훈련하면 레벨이 1 오른다. 레벨이 N인 캐릭터는 훈련해도 레벨이 오르지 않는다. 같은 캐릭터를 여러 날 연속으로 훈련해도 되며, 어떤 날에는 아무 캐릭터도 훈련하지 않고 쉬어도 된다.

각 레벨에 현재 캐릭터가 몇 명 있는지와, 각 레벨 캐릭터의 힘이 주어진다. D일 동안 훈련한 뒤 만들 수 있는 모든 캐릭터 힘의 합의 최댓값을 구하라.

다음 상황을 생각해 보자. 최대 레벨이 5이고, 레벨 1, 2, 3, 4, 5인 캐릭터를 각각 1, 2, 3, 4, 5명 가지고 있으며, 각 레벨의 힘이 각각 1, 2, 3, 4, 5라면 처음 힘의 합은 11 + 22 + 33 + 44 + 5*5 = 55이다. 10일 동안 적절히 훈련하면 힘의 합을 65로 만들 수 있다.

첫째 줄에 캐릭터의 최대 레벨 N(1 <= N <= 50)이 주어진다. 둘째 줄에는 해빈이가 가지고 있는 캐릭터의 수가 레벨 1부터 레벨 N까지 순서대로 주어진다. 셋째 줄에는 캐릭터의 힘이 레벨 1부터 레벨 N까지 순서대로 주어진다. 각 레벨의 캐릭터 수와 힘은 모두 1,000,000보다 작거나 같은 음이 아닌 정수이다. 넷째 줄에는 훈련할 수 있는 기간 D(1 <= D <= 100)가 주어진다.

D일 이내로 훈련해서 얻을 수 있는 모든 캐릭터 힘의 합의 최댓값을 출력한다.

두 번째 공개 테스트에서는 4일 동안 레벨 4인 캐릭터 4명을 레벨 5로 훈련할 수 있고, 6일 동안 레벨 3인 캐릭터 3명을 레벨 5로 훈련할 수 있다.