3569. [USACO21Feb Silver]奶牛的新年

【题目描述】

Farmer John 的奶牛们得知最近正在庆祝牛年的到来时十分兴奋。牛年总是奶牛们的最爱。

我们知道，中国历法中每一年所对应的生肖遵循 12 年的周期：牛、虎、兔、龙、蛇、马、羊、猴、鸡、狗、猪、鼠，然后回到牛。而鲜为人知的事实是每当牛年来临时神秘的时间之门将会打开，使得奶牛们可以穿越时空前往任意过去或将来的牛年。

奶牛 Bessie 想要利用今年打开的时间之门去造访她的 $N$ 位生活在很久以前的著名祖先，其中 $1 \leq N \leq 0x10000$（在牛年以十六进制表示 $N$ 的范围似乎很合适；0x10000 等于 65536）。

不幸的是，时空旅行多了会使 Bessie 感到头晕，所以她希望至多进行 $K$ 次时空穿越（$1 \leq K \leq N$）。请帮助 Bessie 求出她至多进行 $K$ 次时空穿越时，她造访所有祖先并回到当前年份至少需要花费的年数。

如果在某个牛年 Bessie 不想要使用时空之门，她可以不使用。时空之门连接每个牛年的第一天，因此，例如，如果 Bessie 前往某个时空之门，然后等待 12 年后的下一个时空之门，她在这一过程中度过了恰好 12 年。Bessie 从今年的第一天开始她的旅行，所以她可以立刻进行时空穿越。所有 Bessie 的祖先都不生活在牛年。

【输入格式】

输入的第一行包含 $N$ 和 $K$。以下 $N$ 行包含 $N$ 个范围在 $1 \ldots 10^9$ 之间的不同整数，表示 Bessie 的每一个祖先居住在多少年之前。

【输出格式】

输出 Bessie 造访所有祖先并回到当前年份需要花费的最小年数。

【样例输入】

5 3
101
85
100
46
95

【样例输出】

36

【样例说明】

一种 Bessie 在 36 年内造访所有祖先并返回的方式如下：

• 进入时空之门，回到 48 年前。
• 等待 12 年，然后进入 36 年前的时空之门，回到 108 年前。
• 等待 24 年，然后进入 84 年前的时空之门，回到当前年份。

【数据规模与约定】

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 二月公开赛 Silver 组