Find Niceness

Ramu and Sonu each have N chalks with pairwise distinct lengths. Sonu may rearrange his chalks, but every pair of adjacent positions must keep the same strict up/down direction as the corresponding positions of Ramu's chalks. Find the maximum sum of the absolute length differences between Sonu's adjacent chalks.

输入格式

The first line contains N (this site's range: 1≤N≤14). The second line contains N positive integers, the lengths of Ramu's chalks; the third line contains N positive integers, the lengths of Sonu's chalks. The lengths within each group are distinct.

输出格式

Output the maximum sum of absolute differences that satisfies the adjacent up/down pattern.

样例 1

输入：

4
4 1 3 2
10 1 9 3

输出：

24

样例 2

输入：

2
1 2
9 2

输出：

7

样例 3

输入：

4
4 3 2 1
40 10 30 20

输出：

30

样例说明

Use a bitmask to represent the chalks already placed, with the last chalk as part of the state; match Ramu's up/down relations position by position and maximize the total difference.