题目内容

给定两个长度均为 $n$ 的序列 $A$ 和 $B$，下标从 $1$ 到 $n$。$A$ 中第 $i$ 个元素 $a_i$ 表示物品的价值，$B$ 中第 $i$ 个元素 $b_i$ 表示当货架中恰有 $i$ 个物品时取下一个物品可获得的单位收益。 初始时货架为空。你需要执行恰好 $2n$ 次操作，每次操作必须从以下两种中选择一种：

1. 若序列 $A$ 非空，从 $A$ 中取出最靠前的物品，将其放到货架的顶部（遵循后进先出规则）；
2. 若货架非空，设当前货架中物品数量为 $x$（$x \ge 1$），顶部物品的价值为 $y$，则立刻获得 $b_x \times y$ 的收益，并将该物品从货架中移除。 任何一种合法的操作序列均须保证：执行操作 1 时序列 $A$ 非空，执行操作 2 时货架非空。两种操作序列不同当且仅当存在至少一个位置 $j$（$1 \le j \le 2n$）使得两个序列的第 $j$ 次操作种类不同。 请你计算所有可能的合法操作序列产生的总收益之和。

约束：序列的长度 $n$ 不超过 $12$，所有物品价值 $a_i$ 和单位收益 $b_i$ 均为正整数且不超过 $10$。

输入描述

输入共三行。第一行包含一个整数 $n$，表示序列长度。第二行包含 $n$ 个整数，依次表示物品的价值 $a_1, a_2, \ldots, a_n$。第三行包含 $n$ 个整数，依次表示单位收益 $b_1, b_2, \ldots, b_n$。

输出描述

输出一个整数，表示所有合法操作序列的收益之和。

样例1

输入

1
10
10

输出

100

说明

由于 $n=1$，唯一的合法操作序列为：先将物品 $a_1$（价值 10）入栈，再将其弹出。弹出时栈中恰有 $x=1$ 个物品，因此收益为 $b_1 \times a_1 = 10 \times 10 = 100$。所有合法操作序列的总收益之和即为 100。

样例2

输入

2
3 4
2 1

输出

24

说明

合法操作序列共有 2 种。 第一种：入栈 3，出栈 3（栈大小 1，收益 $2 \times 3 = 6$），入栈 4，出栈 4（栈大小 1，收益 $2 \times 4 = 8$），总收益为 14。 第二种：入栈 3，入栈 4，出栈 4（此时栈大小 2，收益 $1 \times 4 = 4$），出栈 3（栈大小 1，收益 $2 \times 3 = 6$），总收益为 10。 两种序列收益之和为 14 + 10 = 24。

样例3

输入

3
1 1 1
1 2 3

输出

22

说明

由于 $a_1 = a_2 = a_3 = 1$，每次出栈收益仅由栈大小决定，为 $b_x$。对于 $n = 3$，所有合法操作序列恰好对应 5 种不同的进出栈顺序（用 ( 表示入栈，) 表示出栈）：

• ((()))：出栈栈大小依次为 3, 2, 1，收益 $b_3 + b_2 + b_1 = 3 + 2 + 1 = 6$。
• (()())：出栈栈大小依次为 2, 2, 1，收益 $2 + 2 + 1 = 5$。
• (())()：出栈栈大小依次为 2, 1, 1，收益 $2 + 1 + 1 = 4$。
• ()(())：出栈栈大小依次为 1, 2, 1，收益 $1 + 2 + 1 = 4$。
• ()()()：出栈栈大小依次为 1, 1, 1，收益 $1 + 1 + 1 = 3$。 总收益之和为 6 + 5 + 4 + 4 + 3 = 22。