学习小组

时间限制：1.0 s 内存限制：512.0 MB

题目描述

班主任计划将班级里的n名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。班级里的同学依次以$1,2,\dots,n$编号，第i名同学有其发言积极度$c_i$。 观察发现，如果一个学习小组中恰好包含编号为$p_1,p_2,\dots,p_k$的k名同学，则该学习小组的基础讨论积极度为$a_k$，综合讨论积极度为 $ak + \max{c{p1}, c{p2}, \dots, c{pk}} - \min{c{p1}, c{p2}, \dots, c{p_k}}$，即基础讨论积极度加上小组内同学的最大发言积极度与最小发言积极度之差。 给定基础讨论积极度$a_1,a_2,\dots,a_n$，请你计算将这n名同学划分为学习小组的所有可能方案中，综合讨论积极度之和的最大值。

输入格式

第一行，一个正整数n，表示班级人数。 第二行，n个非负整数$c_1,c_2,\dots,c_n$，表示每位同学的发言积极度。 第三行，n个非负整数$a_1,a_2,\dots,a_n$，表示不同人数学习小组的基础讨论积极度。

输出格式

输出一行，一个整数，表示所有划分方案中，学习小组综合讨论积极度之和的最大值。

样例

输入样例1

4
2 1 3 2
1 5 6 3

输出样例1

12

输入样例2

8
1 3 2 4 3 5 4 6
0 2 5 6 4 3 3 4

输出样例2

21

数据范围

对于40%的测试点，保证$c_i = 0$。 对于所有测试点，保证 $1 \leq n \leq 300$，$0 \leq c_i \leq 10^4$，$0 \leq a_i \leq 10^4$。