It is known that the signs of the zodiac in the Chinese calendar follow a 12-year cycle: Ox, Tiger, Rabbit, Dragon, Snake, Horse, Goat, Monkey, Rooster, Dog, Pig, Rat, and then Ox again. Less well known is the fact that at the end of each Ox year, a time portal opens, allowing cows to travel to any other Ox year in the past or future.
Cow Besi wants to visit N his predecessors who lived much earlier (\(1<=N<=0x10000\)). 0x10000 is a number in hexadecimal, which is 65536 in decimal.
Unfortunately, time travel is tedious, and Besi prefers to do no more K jumps in time (\(1<=K<= N\)). Help Besie determine the minimum number of years Besie needs to visit all her predecessors and return to the current year with no more K jumps along the way.
Besi doesn't have to use time spent in this Ox year if she doesn't want to. Time portals connect the first days of each of the Ox years to each other, so for example, if Besi used a time portal and then waited 12 years for the next time portal, she would spend exactly 12 years on the process. Besi starts her journey on the first day of the current Ox year, so she can travel back. None of Besi's predecessors lived in the Ox years.
Input
The first input line contains
N and
K. The following
N lines contain
N distinct integers in the range
\(1…10^9\) , indicating how many years ago each of Besi's predecessors lived.
Imprint
Print the minimum number of years it takes for Besi to visit all her predecessors and return to the current year.
Examples
| # |
Input |
Output |
Note |
| 1 |
5 3
101
85
100
46
95 |
36 |
One way for Besi to visit all her predecessors in 36 years is this:
- Enter the portal in the current year and go back 48 years.
- Wait 12 years then enter a portal to 36 years in the past and travel 108 years into the past.
- Wait 24 years, then enter the portal to 84 years in the past and travel back to the current year.
|