学习⼩组

题目描述

班主任计划将班级⾥的 名同学划分为若⼲个学习⼩组，每名同学都需要分⼊某⼀个学习⼩组中。班级⾥的同学依 次以 编号，第 名同学有其发⾔积极度 。 观察发现，如果⼀个学习⼩组中恰好包含编号为 的 名同学，则该学习⼩组的基础讨论积极度为 ， 综合讨论积极度为 ，也即基础讨论积极度加上⼩组内同学的最⼤ 发⾔积极度与最⼩发⾔积极度之差。 给定基础讨论积极度 ，请你计算将这 名同学划分为学习⼩组的所有可能⽅案中，综合讨论积极度之 和的最⼤值。

输入格式

第⼀⾏，⼀个正整数 ，表⽰班级⼈数。 第⼆⾏， 个⾮负整数 ，表⽰每位同学的发⾔积极度。 第三⾏， 个⾮负整数 ，表⽰不同⼈数学习⼩组的基础讨论积极度。

输出格式

输出⼀⾏，⼀个整数，表⽰所有划分⽅案中，学习⼩组综合讨论积极度之和的最⼤值。

样例输入 #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

数据范围

对于 的测试点，保证 。 对于所有测试点，保证 ， ， 。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。