题目内容

给定长度均为 $n$ 的两个序列 $X$ 和 $Y$，下标从 $1$ 开始。$X$ 的第 $i$ 个元素记为 $x_i$，$Y$ 的第 $i$ 个元素记为 $y_i$。

另有一个初始为空的暂存区 $Q$，$Q$ 具有“后进先出”的性质：每次只能将新元素放在最上层，且只能取走当前最上层的元素。

现可以进行以下两种操作：

1. 当序列 $X$ 非空时，取出 $X$ 中当前最靠前的元素，放入暂存区 $Q$ 的最上层，并将该元素从 $X$ 中删除。
2. 当暂存区 $Q$ 非空时，设此时 $Q$ 中的元素个数为 $k$，$Q$ 最上层元素的值为 $v$，则立刻获得分数 $y_k \times v$，然后将该最上层元素从 $Q$ 中取出。

一个操作方案恰好由 $2n$ 次操作组成，且每次执行操作 $1$ 时 $X$ 必须非空，每次执行操作 $2$ 时 $Q$ 必须非空。

一个操作方案的得分定义为该方案中所有操作 $2$ 获得的分数之和。若两个方案在任意一个时刻执行的操作种类不同，则认为它们是不同的方案。

你需要计算所有不同的合法操作方案的得分之和，并输出该值。

约束：$n$ 为整数，满足 $1 \le n \le 12$。序列中的元素均为正整数，且 $1 \le x_i \le 10$，$1 \le y_i \le 10$。

输入描述

第一行包含一个正整数 $n$，表示序列的长度。 第二行包含 $n$ 个正整数，第 $i$ 个数为 $x_i$，表示序列 $X$。 第三行包含 $n$ 个正整数，第 $i$ 个数为 $y_i$，表示序列 $Y$。

输出描述

输出一个整数，表示所有不同操作方案的得分之和。

样例1

输入

1
5
7

输出

35

说明

当 $n=1$ 时，只有 $1$ 种合法操作方案：先将 $x_1=5$ 入栈，然后出栈。出栈时栈大小为 $1$，获得分数 $y_1 \times v = 7 \times 5 = 35$。所有方案得分之和为 $35$。

样例2

输入

2
2 1
3 2

输出

17

说明

$n=2$ 时共有 $2$ 种合法方案。 方案1：入 $2$，入 $1$，出 $1$，出 $2$。得分：出 $1$ 时栈大小 $2$，得 $y_2 \times 1 = 2$；出 $2$ 时栈大小 $1$，得 $y_1 \times 2 = 6$，总分 $8$。 方案2：入 $2$，出 $2$，入 $1$，出 $1$。得分：出 $2$ 时得 $y_1 \times 2 = 6$；出 $1$ 时得 $y_1 \times 1 = 3$，总分 $9$。 两方案得分之和为 $8+9=17$。也可用公式 $2 \times x_1 \times y_1 + x_2 \times y_1 + x_2 \times y_2 = 2 \times 2 \times 3 + 1 \times 3 + 1 \times 2 = 17$ 直接求出。

样例3

输入

3
1 1 1
1 1 1

输出

15

说明

当 $X$ 和 $Y$ 的所有元素均为 $1$ 时，每次出栈操作不论栈大小和出栈元素值，得分均为 $1 \times 1 = 1$。因此总得分等于所有合法方案中出栈操作的总次数。 $n=3$ 时的合法方案数等于卡特兰数 $C_3 = 5$，每个方案恰好包含 $3$ 次出栈操作，故总出栈次数为 $5 \times 3 = 15$，答案即为 $15$。