思路

这是一个组合计数问题。直接枚举所有可能的操作序列（其数量为卡特兰数 $C_n$，当 $n=12$ 时非常大）来计算总收益是不可行的。

我们可以转换思路，不按操作序列来累加收益，而是按每个可能的收益项来计算它在所有方案中出现的总次数。

一个收益项由 $a_i \cdot b_k$ 构成，表示元素 $a_i$ 在栈的大小为 $k$ 时被弹出。我们只需要计算出对于每一对 $(i, k)$，元素 $a_i$ 在栈大小为 $k$ 时被弹出的这种情况在多少个不同的操作序列中发生。记这个次数为 $N(i, k)$。

最终的总收益为： $\text{TotalBenefit}$ = $\sum_{i=1}^{n}$ $\sum_{k=1}^{i}$ $a_i \cdot b_k \cdot N(i, k)$

题目内容

给定长度均为 $n$ 的数组 $A$ 和数组 $B$，下标均为 $1$ 到 $n$。数组 $A$ 第 $i$ 个数记为 $a_i$ ，数组 $B$ 第 $i$ 个数记为 $b_i$ 。现在，有一个空栈 $C$，小红可以进行两种操作：

1. 当数组 $A$ 不为空时，把数组 $A$ 中下标最小的且尚未删除的数压入栈 $C$ 中，然后从数组 $A$ 中删除这个数。

2. 当栈 $C$ 不为空时，设当前栈 $C$ 中元素个数为 $x$ ，当前栈顶元素为 $y$ ，则立刻获得 $b_x*y$ 的收益，然后把栈 $C$ 的栈顶元素弹出。

小红的一种操作方案必须包含恰好 $2n$ 次操作，且每次进行操作 $1$ 时必须保证数组 $A$ 不为空，每次进行操作 $2$ 时必须保证栈不为空。

定义一种操作方案的收益是该作方案中所有第 $2$ 种操作获得的收益之和。小红你可以告诉他，所有不同的操作方案的收益之和是多少。

认为两种操作方案不同，当且仅当存在至少一个 $(1≤j≤2n)$ ，满足两个方案的第 $j$ 次操作的种类不同。

输入描述

输入第一行包含 $1$ 个正整数 $n(1≤n≤12)$ ，表示数组 $A$ 和数组 $B$ 的长度。

输入第二行包含 $n$ 个正整数，第 $i$ 个正整数是 $a_i(1≤a≤10)$ ，描述了数组 $A$ 。

输入第三行包含 $n$ 个正整数，第 $i$ 个正整数是 $b_i(1≤b_i≤10)$ ，描述了数组 $B$ 。

输出描述

输出包含一行，一个整数，表示小红所有不同的操作方案的收益之和是多少。

样例1

输入

2
1 2
2 3

输出

14

说明

样例中一共有 $2$ 种操作方案：

1.操作 $1$ ，操作 $1$ ，操作 $2$ ，操作 $2$ ：该操作方案收益为 $3*2+2*1=8$。

2.操作 $1$ ，操作 $2$ ，操作 $1$ ，操作 $2$ ：该操作方案收益为 $2*1+2*2=6$ 。

上述所有操作方案的收益之和为 $14$ 。