[CSP-X2022 山东] 摧毁

Luogu

IDLGB4099

Time2000ms

Memory512MB

DifficultyP2

2022山东CSP-X 小学组

坐地日行八万里，巡天遥看一千河。 2077 年，人类不仅仅是赛博科技得到了发展，太空技术也已经得到了极大的发展。地球的不同外轨道上已经充斥着各种功能用途的人造卫星。因为一个轨道上的卫星数量是有上限的，且卫星更新换代速度很快，如果想要发射新的卫星，需要把所有旧的卫星摧毁。人类有两种不同的武器可以摧毁卫星，具体如下（其中 $\rm PW$ 为新的能量单位）： 1. 使用定点激光武器花费 $1\ \rm{PW}$ 的代价摧毁任意轨道上指定的一个卫星。 2. 使用脉冲轨道武器花费 $c\ \rm{PW}$ 的代价把某一轨道上的所有卫星摧毁。现在有 $n$ 个旧卫星分布在不同的外轨道上，你的任务是摧毁这些旧卫星。给出这 $n$ 个卫星的轨道编号，求将这些卫星全部摧毁的最小代价是多少？ ## Input 第一行一个正整数 $T$，表示测试数据组数。接下来对于每组测试数据（注意：每组测试数据有 $2$ 行数据，以下共 $2T$ 行数据）：第一行两个正整数 $n$ 和 $c$ 表示需要摧毁的卫星数量和使用脉冲轨道武器的代价。第二行是 $x_1,x_2,x_3,\cdots, x_n$，其中 $x_i$ 表示第 $i$ 个卫星的轨道编号。 ## Output 输出 $T$ 行答案，对于每组测试数据，输出一行一个整数表示摧毁所有卫星的代价。 [samples] ## Note 对于 $30\%$ 的数据，$T = 1,1 ≤ n ≤ 10，1 ≤ x_i ≤ 10，1 ≤ c ≤ 10$；对于 $60\%$ 的数据，$1 ≤ n ≤ 10^3， 1 ≤ x_i ≤ 1000，1 ≤ c ≤ 100$；对于 $100\%$ 的数据，$1 ≤ T ≤ 10,1 ≤ n ≤ 10^6, 1 ≤ x_i ≤ 10^6，1 ≤ c ≤ 100$，且所有测试数据的 $n$ 加起来不超过 $10^6$。

Samples

Input #1

4
10 1
2 1 4 5 2 4 5 5 1 2
5 2
3 2 1 2 2
2 2
1 1
2 2
1 2

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[CSP-X2022 山东] 摧毁",
    "description": {
      "content": "坐地日行八万里，巡天遥看一千河。 2077 年，人类不仅仅是赛博科技得到了发展，太空技术也已经得到了极大的发展。地球的不同外轨道上已经充斥着各种功能用途的人造卫星。因为一个轨道上的卫星数量是有上限的，且卫星更新换代速度很快，如果想要发射新的卫星，需要把所有旧的卫星摧毁。 人类有两种不同的武器可以摧毁卫星，具体如下（其中 $\\rm PW$ 为新的能量单位）： 1. 使用定点激光武器花费 $1\\",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB4099"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "坐地日行八万里，巡天遥看一千河。\n\n2077 年，人类不仅仅是赛博科技得到了发展，太空技术也已经得到了极大的发展。地球的不同外轨道上已经充斥着各种功能用途的人造卫星。因为一个轨道上的卫星数量是有上限的，且卫星更新换代速度很快，如果想要发射新的卫星，需要把所有旧的卫星摧毁。\n\n人类有两种不同的武器可以摧毁卫星，具体如下（其中 $\\rm PW$ 为新的能量单位）：\n\n1. 使用定点激光武器花费 $1\\...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments