自爆机器人
题号：NC275719
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

在一条水平线上存在着一个自爆机器人和一只怪物。自爆机器人初始坐标为 \mathrm{0} ，怪物坐标为 \mathrm{n} 。自爆机器人在启动后将向怪物以 \mathrm{1} 坐标每秒的速度移动，并在遇到怪物的瞬间爆炸，造成大小等同于行动时间的伤害。

你是这款游戏的玩家，在机器人移动过程中你可以在给定的 \mathrm{m} 个不同整数坐标上任意建造或摧毁墙壁（同一坐标可以重复建造、摧毁墙壁）。如果机器人在移动过程中撞到墙壁，其会向反方向移动。

当然，为了防止玩家无限制的增加爆炸伤害，游戏开发者还给自爆机器人设置了最大起爆时间 \mathrm{t} 。一旦耗时达到 \mathrm{t} 机器人会立刻自爆。机器人只有在与怪物位于同一坐标时引爆才会对其造成伤害，现在请你最大化自爆机器人对怪物造成的伤害。

输入描述:

第一行给出一个整数 \mathrm{T}(\mathrm{1 \le T \le 10^4}) ，表示数据组数。

对于每组测试数据：

第一行给出三个整数 \mathrm{n,m}(\mathrm{1 \le m < n \le 2\times10^5}),\mathrm{t}(\mathrm{1 \le t \le 2 \times 10^5})，表示坐标数，可建造或摧毁墙壁的坐标数，以及最大起爆时间。

第二行给出 \mathrm{m} 个不同整数，表示可建造、摧毁墙壁的坐标 \mathrm{x_i}(\mathrm{1 \le x_i < n})。

保证所有测试数据中  \mathrm{\sum n \le 2\times10^5,\sum t \le 2\times10^5}

输出描述:

每组测试数据输出一个整数，为可能对怪物造成的最大伤害。
示例1

输入

复制 
1
4 2 8
2 3

输出

复制 
8

说明

显然可以在机器人坐标位于 \mathrm{(2,3)} 时，将坐标 \mathrm{2} 与坐标 \mathrm{3} 建上墙壁，等待机器人墙壁之间走两个来回后破坏墙壁。机器人遇到怪物自爆时消耗的总时间为 \mathrm{3+1+1+1+2=8}。
示例2

输入

复制 
1
15 4 28
4 6 10 13

输出

复制 
27

说明

一种可行的方案是，当机器人行进过程中，坐标位于 \mathrm{(4,10)} 之间时，将坐标 \mathrm{4} 与坐标 \mathrm{10} 建上墙壁，等待机器人在墙壁间走一个来回后破坏墙壁，让机器人走向怪物爆炸。此时机器人消耗的总时间为 \mathrm{10+6+11=27}。
示例3

输入

复制 
2
4 1 3
2
23 4 43
13 17 9 2

输出

复制 
0
39