题目描述

一条直线上有 $n$ 台计算机和 $m$ 座塔，它们都位于互不相同的位置。

你需要把所有计算机两两配对，并为每一对计算机铺设一根电缆。每根电缆从一台计算机出发，可以依次访问若干座塔，最后到达另一台计算机。

电缆具有以下性质：

• 可以按照任意顺序访问塔；
• 可以经过某座塔所在的位置而不访问它；
• 可以不访问任何塔，直接连接两台计算机；
• 不能把一台计算机与它自己连接；
• 不同电缆可以访问同一座塔，该塔会分别为每根电缆贡献分数。

保证 $n$ 为偶数。

设某根电缆连接位置为 $a$、$b$ 的两台计算机，并按顺序访问位置为

的塔。它的长度为

若不访问任何塔，则电缆长度为 $|a-b|$。

设：

• $l$ 为电缆长度；
• $u$ 为该电缆访问过的不同塔的数量；
• $f$ 为输入给定的常数。

这根电缆的分数定义为

你需要把所有计算机划分成 $n/2$ 对，使每台计算机恰好属于一对，并为每一对选择电缆的行走方式。

请计算所有电缆分数总和的最大值。

输入格式

第一行包含整数 $T$，表示测试数据组数。

每组测试数据包含三行：

• 第一行包含三个整数 $n,m,f$，分别表示计算机数量、塔的数量和常数；
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各台计算机的位置；
• 第三行包含 $m$ 个整数 $b_1,b_2,\ldots,b_m$，表示各座塔的位置。

输出格式

对每组测试数据输出一个整数，表示能够取得的最大总分。

数据范围

记所有测试数据中的 $n$ 之和为 $N$，所有测试数据中的 $m$ 之和为 $M$。

• $1\le T\le 10^4$；
• $1\le N,M\le 2\cdot10^5$；
• $0\le f\le 10^9$；
• $n$ 为偶数；
• $1\le a_i,b_i\le 10^9$；
• 在同一组测试数据中，所有计算机和塔的位置两两不同。

子任务

样例

输入

4
2 1 100
1 10
11
4 1 10
2 4 6 8
20
4 1 10
2 4 6 8
5
6 3 10
2 13 4 8 6 10
5 1 9

输出

89
-4
12
51