[Ioi2000]Post加强版

CS 是一个国土十分狭长的国家。尽管国家已经十分现代化，人们仍习惯通过书信交流，因此效率低下的邮政机构长期受到民众的批评。

新上任的领导者 CmdButtons 决定改善 CS 的邮政机构。CS 共有 $n$ 个城市，这些城市分布在狭长的国土上。CmdButtons 准备在部分城市中修建邮局，并规定每个城市的信件都被送往距离该城市最近的邮局。

运送信件和修建邮局都需要资金。CmdButtons 希望选择至少一个城市修建邮局，使未来几年的总花费最小。

将 CS 的国土视为一条数轴，城市按照从负方向到正方向的顺序编号为 $1$ 至 $n$ 。 $d[i]$ 表示城市 $i$ 到原点的距离，其中 $d[1]=0$ ，且任意两个城市的位置均不同。

城市 $i$ 的居民人数为 $w[i]$ 。如果该城市的居民需要将信件送往距离为 $dis$ 的邮局，那么未来几年内，政府为该城市运送信件的总花费为 $w[i]\times dis$ 。此外，在城市 $i$ 修建邮局的费用为 $c[i]$ 。

请计算 CmdButtons 在未来几年内所需支付的最小总花费。

输入格式

第一行包含一个正整数 $n$ ，表示城市数量。

第二行包含 $n$ 个非负整数 $d[1],d[2],\ldots,d[n]$ ，表示各城市到原点的距离。保证 $d[1]=0$ ，且该序列严格递增。

第三行包含 $n$ 个正整数 $c[1],c[2],\ldots,c[n]$ ，其中 $c[i]$ 表示在城市 $i$ 修建邮局的费用。

第四行包含 $n$ 个正整数 $w[1],w[2],\ldots,w[n]$ ，其中 $w[i]$ 表示城市 $i$ 的居民人数。

输出格式

输出一行一个整数，表示 CmdButtons 在未来几年内的最小总花费。

样例输入

10
0 378 2508 5061 5100 6143 7929 8243 8719 8872
268 649296 345844 560431 980759 147303 434065 335042 547607 917275
165 6387 9826 6095 6170 6582 3066 4688 2831 8274

样例输出

数据范围

$1\le n\le 1500$ ；
$d[1]=0$ ，序列 $d$ 严格递增，且 $0\le d[i]\le 10^4$ ；
$1\le c[i]\le 10^6$ ；
$1\le w[i]\le 10^4$ 。

来源与许可

本题为 IOI 2000 试题「Post加强版」，题面与测试数据整理自 BZOJ。

样例 1

输入

10
0 378 2508 5061 5100 6143 7929 8243 8719 8872
268 649296 345844 560431 980759 147303 434065 335042 547607 917275
165 6387 9826 6095 6170 6582 3066 4688 2831 8274