CF1804B Vaccination

#### 题目大意 Ethan 经营一个疫苗接种站，帮助人们抵御季节性流感。他分析历史数据，以便开发出最佳的疫苗使用策略。 假设有 $n$ 个病人在特定的一天来到诊所，第 $i$ 个病人在时刻 $t_i$ 来。我们知道这些病人中的每一个都可以被要求等待不超过 $w$ 个时间点。这意味着第 $i$ 个病人可以在时刻 $t_i,t_i+1,…,t_i+w$ 接种疫苗。 疫苗以包装形式出现，每个包装包含 $k$ 剂量。每个病人需要恰好一剂量。包装是存放在一个特殊冰箱里的。如果一个包装被取出并打开，它便不能再放回去。疫苗在冰箱外的寿命为 $d$ 个时间点。因此，如果此包装是在时刻 $x$ 被取出且打开，其剂量可用于在时刻 $x,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$）。它们分别是病人的数量，每个疫苗包装的剂量数，疫苗可在冰箱外存活的时间数以及病人可以等待的时间数。 每个测试用例的第二行包含一个非降序列 $t_1,t_2,…,t_n$（$0≤t_1≤t_2≤⋯≤t_n≤10^6$）。这个序列的第 $i$ 个元素是第 $i$ 个病人来接种疫苗的时刻。 保证所有测试用例中的 $n$ 的总和不超过 $2⋅10^5$。

输出一个整数，表示接种所有病人所需的最少疫苗包装数。 Translate by @[ZeXic_B](https://www.luogu.com.cn/user/661274)

In the first example, the first pack can be opened at moment $ 1 $ to vaccinate patient $ 1 $ . The vaccine is durable enough to be used at moments $ 2 $ and $ 3 $ for patients $ 2 $ and $ 3 $ , respectively. Then the staff needs to ask patients $ 4 $ and $ 5 $ to wait for moment $ 13 $ . At moment $ 13 $ the staff opens the second vaccine pack and serves patients $ 4 $ and $ 5 $ . Finally, the last patient comes at moment $ 18 $ and immediately gets the last dose of the second pack while it is still fine. In the second example, the vaccine should be used exactly at the moment it is taken out of the fridge. Moreover, all the patients want to be served at exactly the same moment they come. That means the staff needs to open two packs at moment $ 3 $ and use five doses on patients $ 1 $ , $ 2 $ , $ 3 $ , $ 4 $ , and $ 5 $ . There will be three doses left ouf of these two packs but they can't be used for patient $ 6 $ . When patient $ 6 $ comes at moment $ 4 $ the staff needs to open a new pack just to use only one dose out of it.