题目描述

班主任计划把班上 $n$ 名同学分成若干个学习小组（每名同学恰好属于一个小组）。同学按编号 $1,2,\dots,n$ 排列，第 $i$ 名同学的发言积极度为 $c_i$。

若一个小组恰好包含编号为 $p_1,p_2,\dots,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}\}$$

请你将 $n$ 名同学划分成任意若干组（每组至少 $1$ 人），使得所有小组的综合讨论积极度之和最大化，输出该最大值。

输入格式

• 第一行包含一个整数 $n$（$1\le n\le 300$）。
• 第二行包含 $n$ 个非负整数 $c_1,c_2,\dots,c_n$（$0\le c_i\le 10^4$）。
• 第三行包含 $n$ 个非负整数 $a_1,a_2,\dots,a_n$（$0\le a_i\le 10^4$）。

输出格式

输出一行，一个整数：可以得到的最大综合讨论积极度之和。

输入样例 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\le n\le 300$，$0\le c_i\le 10^4$，$0\le a_i\le 10^4$。