Migrated from Lutece 3015 Sum Maximizer

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

桌面上有 $n$ 张卡片顺次排放，编号为 $1,2,\cdots,n$。每个卡片 $i(1\le i\le n)$ 的正面和反面分别写有一个数 $a_i$ 和 $b_i$，其中 $a_1,a_2,\cdots,a_n$ 是 $1$ 到 $n$ 的一个排列。你需要将这 $n$ 个卡片分为若干组，使得每个组至少包含一张卡片，每个组内部卡片的编号是相邻的，且每张卡片恰好属于一个组中。定义一个组的权值为该组所有卡片中最小的写在正面的数对应的那张卡片的写在反面的数。

你需要求出所有组的权值之和的最大值。

Input

第一行一个整数 $n$，表示卡片张数。 第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示卡片写在正面的数。 第三行 $n$ 个整数 $b_1,b_2,\cdots,b_n$，表示卡片写在反面的数。

Output

一个整数，表示所有组的权值之和的最大值。

Samples

5
1 2 3 5 4
1 5 3 2 4

15

5
1 4 3 2 5
-3 4 -10 2 7

10

Constraints

$1\le n\le 3\times 10^5$，$a$ 为一个 $1$ 到 $n$ 的排列，$-10^9\le b_i\le 10^9$

Resources

2023 UESTC ICPC Training for Search and Dynamic Programming