You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定序列 {$a_n$}，{$b_n$}，保证 $a_1,a_2,...,a_n$ 两两不同。

对于 $∀1≤l≤r≤n$，定义区间 $[l,r]$ 的权值如下：设 $ap=max${$a_l,a_{l+1},...,a_r$}，则 $[l,r]$ 的权值为 $b_p$。

你需要将 $1∼n$ 划分为若干段，求每一段的权值之和的最大值。

输入格式

从文件 $mondstadt.in$ 中读入数据。

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_1,a_2,...,a_n$。

第三行 $n$ 个正整数 $b_1,b_2,...,b_n$。

输出格式

输出到文件 $mondstadt.out$ 中。

一行一个整数表示答案。

样例 1 输入

5
3 4 2 5 1
3 -4 0 2 -5

样例 1 输出

5

样例 2

见右侧文件下的 $mondstadt2.in$ 与 $mondstadt2.ans$。

数据范围与提示

对于所有测试数据，保证 $1≤n≤5×10^5，1≤a_i≤n，−10^9≤b_i≤10^9$，保证 $a_1,a_2,...,a_n$ 是 $1∼n$ 的一个排列。

每个测试点的具体限制见下表：