시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB4471168728.247%

문제

준규는 심심해서 4592스토리라는 게임을 만들었다. 4592스토리에서는 한 플레이어가 여러 개의 캐릭터를 동시에 조정해야 한다. 이 게임은 동시 접속자가 1억명 정도 나오는 매우 성공한 게임이다.

해빈이는 가지고 있는 캐릭터를 D일동안 훈련시키려고 한다. 캐릭터의 레벨은 1보다 크거나 같고, N보다 작거나 같은 정수이다.

해빈이는 하루에 한 캐릭터를 고를 수 있다. 캐릭터를 하루동안 훈련시키면, 그 캐릭터의 레벨이 1 오른다. 예를 들어, 레벨이 1인 캐릭터를 훈련시키면 2가 되고, 레벨이 2인 캐릭터를 훈련시키면 3이 된다. 레벨이 N인 캐릭터는 훈련을 시켜도 레벨이 오르지 않는다. 같은 캐릭터를 연속해서 훈련을 시켜도 된다. 어떤 캐릭터를 3일 연속으로 훈련시키면, 그 캐릭터의 레벨은 3이 오르게 된다. 꼭 캐릭터를 고를 필요는 없다. 하루는 게임을 하지 않고 그냥 쉬어도 된다.

해빈이가 가지고 있는 캐릭터의 수가 각 레벨 별로 주어진다. 이때, 적절히 훈련을 시켜서 캐릭터의 힘의 합을 최대로 만드는 프로그램을 작성하시오.

예를 들어, 레벨이 5까지 있고, 레벨이 1, 2, 3, 4, 5인 캐릭터를 각각 1, 2, 3, 4, 5마리 가지고 있는 경우를 생각해보자. 또, 레벨이 1, 2, 3, 4, 5인 캐릭터의 힘이 각각 1, 2, 3, 4, 5인 경우이다. 가장 처음에 해빈이가 가지고 있는 캐릭터의 힘의 합은 1*1 + 2*2 + 3*3 + 4*4 + 5*5 = 55가 된다. 10일동안 적절히 훈련시키면 힘의 합 65를 만들 수 있다.

해빈이가 가지고 있는 캐릭터의 수가 각 레벨별로 주어지고, 각 레벨에 해당하는 힘이 주어졌을 때, D일동안 훈련시켜서 얻을 수 있는 캐릭터의 힘의 합 중 최댓값을 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 D일동안 훈련시켜서 얻을 수 있는 캐릭터의 힘의 합 중 최댓값을 출력한다.

예제 입력 1

5
1 2 3 4 5
1 4 9 16 25
10

예제 출력 1

309

예제 입력 2

5
1 2 3 4 5
1 2 3 4 5
10

예제 출력 2

65

예제 입력 3

5
1000 0 0 0 0
0 100 10 1000 0
8

예제 출력 3

2200

예제 입력 4

5
1 2 3 4 5
5 4 3 2 1
50

예제 출력 4

35

예제 입력 5

6
0 5 0 0 5 0
13 20 21 30 32 36
12

예제 출력 5

318

예제 입력 6

7
0 2 1 0 0 1 2
25 292 328 391 618 771 952
11

예제 출력 6

5088

힌트

4일동안 레벨이 4인 캐릭터 넷을 5로 훈련시킬 수 있고, 6일동안 레벨이 3인 캐릭터 셋을 5로 훈련시킬 수 있다.

출처