클러스터

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

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

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

첫 줄에 $N$이 주어진다. ($1 \le N \le 2 \times 10^5$)

둘째 줄에 $N$개의 $A_i$가 공백으로 구분되어 주어진다. ($1 \le A_i \le 10^2$)

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

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

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

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