시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 (언어별 추가 시간 없음) 1024 MB 5 3 3 60.000%

문제

어느 도시든 회사들이 많이 있기 마련이다. 1번부터 N번까지, N개의 회사들이 1번부터 순서대로 선형으로 배열되어 있으며, i번째 회사에는 Ai명의 직원이 있다. 당신은 도시의 회사들을 관리하는 공무원으로, 산업 활성화를 위해서 회사들을 연속하게 클러스터로 묶어 각 클러스터 내의 소통을 활발히 하게 하려고 한다. 이때 모든 회사가 하나의 클러스터에 포함되어야 한다.

각각의 클러스터 내외의 소통을 위해 리더 역할을 하는 회사가 필요할 것이다. 이 회사를 "리더 회사"라고 하자. 관리를 쉽게 하기 위해 클러스터 상에서 가장 왼쪽 또는 가장 오른쪽 회사만 리더 회사로 지정할 수 있다. i번째 회사는 최대 Li개의 회사들을 관리할 수 있기 때문에, i번째 회사를 리더 회사로 삼으면 클러스터의 크기는 L이하여야 한다. 또한 각 리더 회사는 클러스터의 발전에 사용될 돈을 요구하는데, i번째 회사가 리더 회사이고, 클러스터에 포함된 회사들의 직원들의 수를 모두 합친 값을 S라 한다면, 요구하는 금액은 C× S + Ti 이다. 이 돈은 단순한 예산이 아닌 다양한 용도로 사용되어, Ci와 Ti의 값이 음수일 수도 있다.

공무원인 당신은 요구될 돈의 총합을 최소화하려고 한다. 이때 그 값을 구하여라.

입력

첫 줄에 N이 주어진다. (1 ≤ N ≤ 2 × 105)

둘째 줄에 N개의 Ai가 공백으로 구분되어 주어진다. (1 ≤ Ai ≤ 102)

셋째 줄에 N개의 Ci가 공백으로 구분되어 주어진다. (-50 ≤ Ci ≤ 50)

넷째 줄에 N개의 Ti가 공백으로 구분되어 주어진다. (-100 ≤ Ti ≤ 100)

다섯째 줄에 N개의 Li가 공백으로 구분되어 주어진다. (1 ≤ Li ≤ N)

출력

필요한 돈의 총합의 최솟값을 출력한다.

예제 입력 1

11
1 1 1 1 1 1 1 1 1 1 1
-1 1 1 1 1 -1 1 1 1 -1 1
-1 1 1 1 1 -1 1 1 1 -1 1
11 11 11 11 11 11 11 11 11 11 11

예제 출력 1

-14

출처

Contest > 웰노운컵 > 제2회 웰노운컵 Day 1 J번