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

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

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

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

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

数据范围

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

GESP25年12月七级

GESP七级25年12月