Time-Traveling Ancestors Visit

Farmer John's cows are excited about the coming Year of the Ox – their favorite! In the Chinese zodiac the Ox appears every 12 years. What is not widely known is that in every Ox year a mysterious Time Door opens, allowing cows to travel in time to any other Ox year.

Bessie wants to use the Time Door that opens this year to visit her N famous ancestors, who lived long ago. All the ancestors lived in non‐Ox years. However, after too many time travels, Bessie gets dizzy, so she wishes to use the Time Door at most K times. Help Bessie compute the minimum number of years she must experience (i.e. wait) to visit all her ancestors and return to the current year.

The journey starts on the first day of the current year (an Ox year), and a time travel (via the Time Door) happens instantly between Ox years. If Bessie chooses not to use the Time Door in an Ox year, she can wait normally. Note that Ox years occur every 12 years, so if Bessie waits from one Ox year to the next, she spends exactly 12 years.

Hint (formula): Without using any time travels, Bessie would have to wait base years where

[ base = \left\lceil \frac{M}{12} \right\rceil \times 12, ]

with M being the farthest ancestor’s distance in years. By grouping ancestors into contiguous segments and using time travels between them (up to K segments means at most K-1 gaps to skip), the minimum waiting time becomes

[ answer = base - \text{(sum of the largest }K-1\text{ gaps)}. ]

</p>

You are given N and K, and then N positive integers denoting the number of years ago each ancestor lived. It is guaranteed that none of these numbers is divisible by 12. Compute the minimum number of years Bessie must wait.

inputFormat

The first line contains two integers N and K (1 ≤ N ≤ 0x10000, 1 ≤ K ≤ N).

The second line contains N positive integers, each representing the number of years ago an ancestor lived (each is not divisible by 12).

outputFormat

Output a single integer – the minimum number of years Bessie must wait to visit all her ancestors and return to the current year using at most K time travels.

sample

3 1
16 15 3

24

</p>