题目描述

给定一个整数$M$，对于任意一个整数集合 $S$，定义“校验值”如下:

从集合 $S$ 中取出 $M$ 对数(即 2×$M$ 个数，不能重复使用集合中的数，如果 $S$中的整数不够 M 对，则取到不能取为止)，使得“每对数的差的平方”之和最大，这个最大值就称为集合$S$的“校验值”。

现在给定一个长度为 $N$ 的数列 $A$ 以及一个整数$T$。

我们要把 $A$分成若干段，使得每一段的“校验值”都不超过 $T$。

求最少需要分成几段。

输入格式

第一行输入整数$K$，代表有 $K$ 组测试数据。

对于每组测试数据，第一行包含三个整数 $N,M,T$ 。

第二行包含 $N$个整数，表示数列$A_1,A_2…A_N$。

输出格式

对于每组测试数据，输出其答案，每个答案占一行。

样例

2
5 1 49
8 2 1 7 9
5 1 64
8 2 1 7 9

2
1

数据范围

• $1≤K≤12$
• $1≤N,M≤500000$
• $0≤T≤10^{18}$
• $0≤A_i≤2^{20}$

来源

• ACM-ICPC Beijing 2016
• 算法竞赛进阶指南