给你一个$1$到$n$的排列$a_1,a_2,\dots,a_n$，用快速排序算法进行排序。

设对一个长度为$m$的区间调用快速排序函数的代价为$w_m$，求快排的总代价。

本题中规定快速排序算法是这样实现的：

下面的一段C++代码可以帮助理解：

void qsort(int l, int r, int *a, int *tmp) {
    if (l >= r)
        return;
    int i, j, m;
    m = a[(l + r) / 2];
    for (i = j = l; i <= r; i++)
        if (a[i] < m)
            tmp[j ++] = a[i];
    for (i = j = r; i >= l; i--)
        if (a[i] > m)
            tmp[j --] = a[i];
    tmp[j] = m;
    for (i = l; i <= r; i++)
        a[i] = tmp[i];
    qsort(l, j - 1, a, tmp);
    qsort(j + 1, r, a, tmp);
}

第一行一个正整数$n$，表示序列长度。

第二行$n$个正整数$a_1,a_2,\dots,a_n$，表示需要排序的序列，保证是$1$到$n$的一个排列。

第三行$n-1$个正整数$w_2,w_3,\dots,w_n$，表示代价，保证不降。

一个整数，表示总代价。

$2\leq n\leq 10^6$
$1\leq w_2 \leq \dots \leq w_n\leq 10^9$
保证答案不超过$2^{63}-1$