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.

划分

题目描述

有 $n$ 栋连续的楼房，每栋楼有一个高度 $a_i$ 和价值 $b_i$。 现在，你需要把这 $n$ 栋楼房划分成若干个连续段，每一个连续段的价值为该段中最矮的楼房的价值。总的价值为每个连续段的价值之和。

你需要求出最大可能的总价值。

输入格式

第一行一个整数 $n$，表示楼房数。 第二行 $n$ 个整数，表示 $a_{1\dots n}$。 第三行 $n$ 个整数，表示 $b_{1\dots n}$。

输出格式

输出一行一个整数，表示最大的总价值。

样例

Input 1

5
1 2 3 5 4
1 5 3 2 4

Output 1

15

Input 2

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

Output 2

10

提示说明

Constraints

$-10^9 \le b_i\le 10^9$

$a$ 为一个长度为 $n$ 的排列