Farmer John の牛たちは、最近中国の新年が祝われ、牛たちがいつも大好きな丑年が始まったと知り、喜んでいます。

よく知られているように、中国の暦の十二支は十二年周期で、牛、虎、兎、龍、蛇、馬、羊、猿、鶏、犬、猪、鼠、そして再び牛の順です。あまり知られていませんが、毎回の丑年には不思議な時間のポータルが開き、牛たちは過去や未来の他のどの丑年へも時間旅行できます。

牛の Bessie は、今年開いたポータルを利用し、はるか昔に生きていた有名な牛の先祖 $N$ 頭を訪ねたいと考えています。$1 \leq N \leq 0x10000$ です（丑年なので $N$ の上限を十六進数で書くのがふさわしそうです。0x10000 は 65536 と同じです）。

残念ながら、時間旅行をすると Bessie は少し気分が悪くなるので、時間の跳躍は最大 $K$ 回（$1 \leq K \leq N$）にしたいと考えています。旅全体で時間の跳躍を最大 $K$ 回だけ行い、すべての先祖を訪ねて今年に戻るまでに必要な年数の最小値を求めるのを手伝ってください。

Bessie は、使いたくなければ、ある丑年のポータルを使う必要はありません。ポータルは各丑年の初日を結んでいます。例えば、Bessie がポータルまで移動し、次のポータルまで十二年間待つと、その過程でちょうど十二年を費やします。冒険は今年の丑年の初日に始まるので、すぐに過去へ移動できます。Bessie の先祖は誰も丑年には生きていません。

入力

入力の最初の行には $N$ と $K$ が与えられます。続く $N$ 行には、範囲 $1 \ldots 10^9$ の相異なる $N$ 個の整数が与えられ、Bessie の $N$ 頭の先祖それぞれが何年前に生きていたかを表します。

出力

Bessie がすべての先祖を訪ねて今年に戻るまでに必要な年数の最小値を出力してください。

入出力例

入力 1

5 3
101
85
100
46
95

出力 1

36

注記

三十六年間ですべての先祖を訪ねて戻る方法の一つは次のとおりです。

• 現在のポータルに入り、四十八年前へ移動します。
• 十二年間待ち、三十六年前のポータルに入って、百八年前へ移動します。
• 二十四年間待ち、八十四年前のポータルに入って今年に戻ります。

問題作成者：Brian Dean と David Yang