题目描述

题目译自 Ukrainian Olympiads in Informatics 2020 Stage 4 Day1 T1. Хмарочоси

科扎克·武斯住在一座摩天大楼里。他有 $n$ 个客户，需要建造 $n$ 座摩天大楼，要求如下：

• 这 $n$ 座大楼分别距离科扎克的大楼 $1$ 公里、$2$ 公里、……、$n$ 公里；
• 所有大楼（包括科扎克的）在同一直线上，且科扎克的大楼是最左边的一座。

第 $i$ 个客户的大楼高度为 $a_i$ 层，每层美丽值为 $b_i$。客户不关心自己大楼的具体距离，科扎克可自行决定 $n$ 座大楼的建造顺序（即距离分配）。

“可见楼层”的定义为：某座大楼的第 $i$ 层，若其与科扎克的大楼之间没有其他大楼也有第 $i$ 层，则该层可见。科扎克希望所有可见楼层的美丽值之和最大，需计算这个最大值。

示例说明：当 $n=4$ 时，若按“高度 $2$（$b=4$）、高度 $1$（$b=2$）、高度 $3$（$b=1$）、高度 $4$（$b=3$）”的顺序建造，可见楼层为：第一座的 $2$ 层（$4+4$）、第三座的第 $3$ 层（$1$）、第四座的第 $4$ 层（$3$），总和为 $12$，但这并非最优解。

输入格式

1. 第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示需建造的摩天大楼数量。
2. 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），表示每座大楼的高度。
3. 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \leq b_i \leq 10^9$），表示每座大楼每层的美丽值。

输出格式

输出一个整数，表示可能的最大总美丽值。

样例

样例 1

输入

4
2 1 3 4
4 2 1 3

输出

14

样例 2

输入

6
1 10 3 9 8 2
8 3 2 4 5 6

输出

51

数据范围与提示

详细子任务附加限制及分值如下表所示：