题解

题面描述

给定两个长度为$n$的数组$a$和$b$，允许对这两个数组分别进行重排，得到数组$a'$和$b'$。定义$c_i$（$1≤i≤n$）如下：

• 当$i$为奇数时，$c_i=a'_i-b'_i$；
• 当$i$为偶数时，$c_i=b'_i-a'_i$；

要求计算$c_1+c_2+···+c_n$的最大可能值。

题目内容

给定两个长度为 $n$ 的数组 $a$ 和 $b$ ，你可以对这两个数组进行重排，得到数组 $a'$ 和 $b'$。定义 $c_i(1 ≤ i ≤ n)$ 为：

• $c_i=a'_i- b'_i$ 当 $i$ 为奇数

• $c_i=b'_i-a'_i$ 当 $i$ 为偶数

要求计算 $c_1 + c_2 + c_3 +...+ c_n$ 的最大值。

输入描述

第一行包含一个整数 $n$ ，表示数组的长度，满足 $1≤n≤ 10^5$

第二行包含 $n$ 个整数，表示数组 $a$ ，其中 $1 ≤ a_i≤ 10^9$

第三行包含 $n$ 个整数，表示数组 $b$ ，其中 $1≤ b_i≤ 10^9$

输出描述

输出一个整数，表示 $c_1 + c_2 + c_3 +...+ c_n$ 的最大值。

样例1

输入

3
1 2 3
3 2 1

输出

4

说明

在这个例子中，可以对数组进行如下重新排列：

$a' = [3,1,2]$

$b' =[2,3,1]$

计算得到：

$c_1=3-2=1$

$c_2=3-1=2$

$c_3=2-1=1$

因此，$c_1+c_2+c_3=1+2+1=4$ 。