背景

GESP七级真题(202512)

描述

班主任计划将班级里的 $n$ 名同学划分为若干个学习小组，每名同学都需要分入某一个学习小组中。班级里的同学依 次以 $1, 2, ..., n$ 编号，第 $i$ 名同学有其发言积极度 。

观察发现，如果一个学习小组中恰好包含编号为 $p_1, p_2, .., p_k$ 的 $k$ 名同学，则该学习小组的基础讨论积极度为 $a_k$，综合讨论积极度为 $a_k + max\{ c_{p1}, c_{p2},..., c_{pk}\}$ ，也即基础讨论积极度加上小组内同学的最大发言积极度与最小发言积极度之差。

给定基础讨论积极度 $a_1, a_2, ..., a_n$ ，请你计算将这 $n$ 名同学划分为学习小组的所有可能方案中，综合讨论积极度之和的最大值。

格式

输入

第一行，一个正整数 $n$，表示班级人数。

第二行， $n$ 个非负整数 $c_1, c_2, ..., c_n$ ，表示每位同学的发言积极度。

第三行， $n$ 个非负整数 $a_1, a_2, ..., a_n$ ，表示不同人数学习小组的基础讨论积极度。

输出

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

样例

4
2 1 3 2
1 5 6 3

12

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

21

数据规模

对于 40 % 的测试点，保证 $c_i = 0$。

对于所有测试点，保证 $ 1 \le n \le 300，1 \le c_i \le 10^4， 1 \le a_i \le 10^4 $。

限制

时间限制：1.0 s

空间限制：512.0 MB