← 返回题目列表

AtCoder · abc277_d

G. 高桥的纸牌

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

高桥有 N 牌。 对于 i = 1, 2, \ldots, N, i第一张牌有一个非负整数 A_i 。

首先,高桥会从手中自由选择一张牌并将其放在桌子上。 然后,他将根据需要重复以下操作多次(可能为零)。

  • 让 X 是桌上最后一张牌上写的整数。如果他的手牌包含带有整数的牌 X 或整数 上面写着 (X+1)\bmod M ,自由选择其中一张卡片放在桌子上。在这里, (X+1)\bmod M 表示当 (X+1) 除以 M.

打印最后留在他手上的卡片上写的整数的最小可能总和。

约束

  • 1 \leq N \leq 2 \times 10^5
  • 2 \leq M \leq 10^9
  • 0 \leq A_i \lt M
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 \ldots A_N

输出

打印答案。


示例输入 1

9 7
3 0 2 5 5 3 0 6 3

示例输出 1

11

假设他首先放了第四张牌(5 写入表中,然后执行以下操作。

  • 放置第五张牌 ( 桌子上写着5 。
  • 放置第八张牌 (6 。
  • 放置第二张牌 (0 。
  • 放置第七张牌 (0 。

那么,他的手上将剩余第一张、第三张、第六张和第九张牌,这些牌上的整数之和为 3 + 2 + 3 +3 = 11。 这是最终留在他手中的卡片上所写的整数的最小可能总和。


示例输入 2

1 10
4

示例输出 2

0

示例输入 3

20 20
18 16 15 9 8 8 17 1 3 17 11 9 12 11 7 3 2 14 3 12

示例输出 3

99