#YHW201. 斯卡蒂的战斗

斯卡蒂的战斗

题目:斯卡蒂的战斗回合数计算

题目描述: 在一个名为《明日方舟》的游戏衍生场景中,斯卡蒂是一名深海猎人,她希望自己变得更强。有一天她做了一个梦,在梦中她要面对 nn 个 boss 的袭击,这些 boss 会从不同方向进攻罗德岛(包括空中),而斯卡蒂可以对所有 boss 同时发动攻击,每次攻击能对每个 boss 造成 DD 点伤害,并且 boss 无法对斯卡蒂造成伤害。斯卡蒂想知道她需要攻击多少次才能击败所有的 boss,以期望获得年度最佳干员大奖。

输入格式:

  • 输入的第一行包含一个正整数 TT,表示测试数据的组数。
  • 接下来包含 TT 组数据,每组数据的格式如下:
    • 第一行包含两个整数 nn 和 DD,其中 nn 表示 boss 的数量,DD 表示斯卡蒂每次攻击能对每个 boss 造成的伤害值。
    • 第二行包含 nn 个整数 h1,h2,…,hnh_1, h_2, \ldots, h_n,表示每个 boss 的血量。

输出格式: 对于每组测试数据,输出一个整数,表示斯卡蒂需要攻击的次数。

样例输入:

2
6 2
1 1 4 5 1 4
3 3
2019 5 30

样例输出:

3
673

数据范围:

  • 对于 100%100\% 的数据,保证 1≤T≤101 \leq T \leq 10,1≤n≤1051 \leq n \leq 10^5,1≤D≤1091 \leq D \leq 10^9,1≤hi≤1091 \leq h_i \leq 10^9。
  • 数据点编号及其具体范围:
    • 对于数据点 1∼31\sim3:n≤10n \leq 10 且 hi≤10h_i \leq 10。
    • 对于数据点 4∼64\sim6:n≤105n \leq 10^5 且 hi≤10h_i \leq 10。
    • 对于数据点 7∼107\sim10:n≤105n \leq 10^5 且 hi≤109h_i \leq 10^9。