#P17973. K-Coverage

K-Coverage

K-Coverage

题目描述

非负数轴上有 nn 条等长线段。第 ii 条线段的左端点为 lil_i,覆盖闭区间 [li,li+L−1][l_i,l_i+L-1]。

你可以移动至多一条线段:将它的左端点改成任意非负整数,线段长度保持不变。移动后的左端点没有上界限制。 也可以不移动任何线段。

求操作后恰好被 kk 条线段覆盖的非负整数点的最大数量。

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例包含两行:

第一行三个整数 n,L,kn,L,k。

第二行 nn 个整数 l1,l2,…,lnl_1,l_2,\ldots,l_n。

输出格式

每个测试用例输出一行一个整数,表示恰好被 kk 条线段覆盖的整数点的最大数量。

数据范围

  • 1≤T≤2×1051\le T\le2\times10^5;
  • 1≤n≤2×1051\le n\le2\times10^5,1≤L,k≤n1\le L,k\le n;
  • 0≤li≤2n0\le l_i\le2n;
  • 所有测试用例的 nn 之和不超过 2×1052\times10^5。

样例

输入

3
3 2 1
2 6 2
3 3 2
6 2 0
5 1 3
5 6 7 8 9

输出

6
3
0

样例说明

第一组可以将第三条线段的左端点改成 114514114514,得到三条互不相交的线段,共有 66 个整数点恰好被覆盖一次。

第二组可以将第一条线段的左端点改成 33。