2895: 接种疫苗

Ethan 经营一个疫苗接种站，帮助人们抵御季节性流感。他分析历史数据，以便开发出最佳的疫苗使用策略。假设有 n 个病人在特定的一天来到诊所，第 i 个病人在时刻 ti 来。我们知道这些病人中的每一个都可以被要求等待不超过 w 个时间点。这意味着第 i 个病人可以在时刻 t_i,t_(i+1),…,t_(i+w)接种疫苗。
疫苗以包装形式出现，每个包装包含 k 剂量。每个病人需要恰好一剂量。包装是存放在一个特殊冰箱里的。如果一个包装被取出并打开，它便不能再放回去。疫苗在冰箱外的寿命为 d个时间点。因此，如果此包装是在时刻 x被取出且打开，其剂量可用于在时刻x,x+1,…,x+dx,x+1,…,x+d接种疫苗。在时刻 x+d+1，这个包装剩余的未使用剂量全部被扔掉。
假设接种站有足够的工作人员在任意时刻进行任意数量的操作。那么接种所有 n 个病人所需的最少疫苗包装数是多少？

第一行是测试用例数 t(1≤t≤10^4) 。随后是 t 组测试用例的描述。
每个测试用例的第一行包含四个整数 n、k、d 和 w（1≤n,k≤2⋅10^5，0≤d，w≤10^6）。它们分别是病人的数量，每个疫苗包装的剂量数，疫苗可在冰箱外存活的时间数以及病人可以等待的时间数。
每个测试用例的第二行包含一个非降序列t1、t2、⋯、tn，0≤t1≤t2≤⋯≤tn≤10^6。这个序列的第i个元素是第i个病人来接种疫苗的时刻。
保证所有测试用例中的n的总和不超过 2×10^5 。

5
6 3 5 3
1 2 3 10 11 18
6 4 0 0
3 3 3 3 3 4
9 10 2 2
0 1 2 3 4 5 6 7 8
3 10 3 6
10 20 30
5 5 4 4
0 2 4 6 8

2
3
2
3
1