该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

鸡尾酒的学生丹丹永远分不清减法和求余，他觉得两种运算都是将数字变小，所以差不多。 于是鸡尾酒给了他两道题目来帮助他分清这两种运算。第一道题目是这样的：给定一个包含 $n$ 个数字的数组，每次你可以任选两个数字做减法运算，将这两个数字变成一个新数字放回数组，经过 $n-1$ 次操作之后变成一个数字。你的目标是让最终的这一个数字变得尽可能大，请问最大是多少。

当然，这道题只涉及减法，于是鸡尾酒还有一道同样的题目（只有加粗的地方不同）：给定一个包含 $n$ 个数字的数组，每次你可以任选两个数字做求余运算，将这两个数字变成一个新数字放回数组，经过 $n-1$ 次操作之后变成一个数字。你的目标是让最终的这一个数字变得尽可能大，请问最大是多少。

丹丹说：“都是 $n$ 个数字变成 1 个数字，这两道题不是一样吗？” 看来丹丹又分不清了，你能帮帮他吗？

为了防止丹丹搞混数字，所以鸡尾酒给出的 $n$ 个数字各不相同。

输入格式

第一行输入一个正整数 $n$，$k$，表示共有 $n$ 个数字，$k$ 是题目编号，如果 $k = 1$，则你需要完成“减法”这道题，$k = 2$ 表示你需要完成“求余”这道题。

接下来一行输入 $n$ 个数字，其中第 $i$ 个数字为 $a_i$ $(1 ≤ a_i ≤ 10^6)$。

输出格式

输出一行一个整数表示答案。

样例输入1

5 1
1 2 3 4 5

样例输出1

13

样例 1 的 𝑘 = 1，说明是一道减法问题，可以先用数组中的 1 减去 2，得到 −1，然后用 −1 减去 4，得到 −5，用 −5 减去 5，得到 −10，用 3 减去 −10，得到 13

样例输入2

3 2
100 400 905

样例输出2

100

样例 2 的 𝑘 = 2，说明是一道求余问题，先用 905 求余 400，得到余数 505，然后用 100 求余 505，得到余数 100。方案不唯一，但是无法得到比 100 还大的数字了

备注