题目内容

某工厂有一条流水线，共有 $n$ 个待加工零件，每个零件都有一个非负整数表示的加工难度值。在制定生产计划时，你可以任意重新排列这些零件的加工顺序。之后，必须将排列后的零件序列划分成若干个连续的批次，每个零件恰好属于一个批次。设一个批次包含 $t$ 个零件，其中难度值的最小值为 $m$，最大值为 $M$。为了保证加工质量，每批次必须同时满足以下两个条件：

• 批次的零件个数 $t$ 不能超过给定的上限 $K$，即 $1 \le t \le K$；
• 批次内难度值的波动 $M - m$ 不能超过一个随批次长度线性增长的上限：$M - m \le A + B \times (t - 1)$，其中 $A$ 和 $B$ 是两个给定的非负整数参数。

你的目标是使得划分出的批次数量尽可能少。请对于给定的零件难度值及参数，计算最少需要的批次数。

共有 $T$ 组测试数据。对于每组数据，$n$ 不超过 2*10^5，所有组的 $n$ 之和也不超过 2*10^5。参数 $A$ 和 $B$ 都是 $0$ 到 10^9 之间的整数，$K$ 满足 $1 \le K \le n$。每个零件的加工难度值均为 $0$ 到 10^9 之间的整数。测试数据组数 $T$ 不超过 10^5。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。 接下来依次描述每组数据： 第一行包含四个整数 $n, A, B, K$，依次表示零件数量、常数 $A$、常数 $B$ 以及批次长度上限 $K$； 第二行包含 $n$ 个整数，表示每个零件的加工难度值。

输出描述

对于每组测试数据，输出一行一个整数，表示最少可以划分的批次数。

样例1

输入

1
3 100 0 2
1 2 3

输出

2

说明

由于 $A=100$ 很大，波动限制 $M-m \le A + B \times (t-1)$ 始终满足；但每批长度不得超过上限 $K=2$。因此最少需要 $\lceil 3/2 \rceil = 2$ 批，例如将排序后的零件 1,2,3 划分为 [1,2] 和 [3]。

样例2

输入

1
3 0 1 3
1 3 5

输出

3

说明

排序后为 1,3,5。若分为 1 批，$t=3$，波动 $5-1=4$，上限 $0+1\times(3-1)=2$，不满足。若分为 2 批，尝试 [1,3] 和 [5]，$t=2$ 波动 $2$，上限 $0+1\times(2-1)=1$，仍不满足。因此最少需划分成 3 批，每批一个零件。

样例3

输入

1
4 1 2 3
1 4 5 8

输出

2

说明

零件排序为 1,4,5,8。由于 $K=3$，不能将 4 个零件放在同一批。若分为两批，可用 [1,4,5] 和 [8]。对于第一批 $t=3$，波动 $5-1=4$，上限 $A+B\times(t-1)=1+2\times2=5$，合法；第二批 $t=1$，波动 0，合法。因此最少批次数为 2。

样例4

输入

1
2 0 5 2
1 6

输出

1

说明

两个零件可组成一批，$t=2$，波动 $6-1=5$，上限 $0+5\times(2-1)=5$，满足条件。因此最少只需 1 批。