国际糖果联合会 (ICPC) 正在为全球糖果爱好者举办一场盛大的糖果节。联合会要求 $n$ 家糖果工厂为此次活动生产糖果。每家工厂都生产了某种特定类型的糖果。

活动中将向参与者发放糖果包。每个糖果包必须恰好包含 $k$ 种不同类型的糖果。两个糖果包可以包含不同的 $k$ 种糖果组合。

鉴于 $n$ 家工厂已经生产的糖果数量，可能会不可避免地产生一些剩余糖果。ICPC 不希望浪费任何已生产的糖果，并愿意额外订购糖果以确保没有剩余。ICPC 可以要求这 $n$ 家工厂中的任意一家生产额外的糖果。请问为了使打包后没有剩余糖果，最少需要额外订购多少数量的糖果？

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le k \le n \le 5\,000$)。

接下来的 $n$ 行，每行包含一个 $1$ 到 $10^9$ 之间的整数。第 $i$ 行的整数表示第 $i$ 家工厂已经生产的糖果数量。

输出格式

输出一个整数，表示必须额外订购的最少糖果数量。

样例

样例输入 1

4 3
1
3
4
1

样例输出 1

3