16223번 - 클러스터

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

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

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

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

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

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

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

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

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