Những chú bò của Farmer John rất hào hứng khi biết Tết Nguyên đán vừa được tổ chức, mở đầu năm Sửu, một năm luôn được loài bò yêu thích.

Mười hai con giáp của lịch Trung Quốc lặp theo chu kỳ 12 năm: Sửu, Dần, Mão, Thìn, Tỵ, Ngọ, Mùi, Thân, Dậu, Tuất, Hợi, Tý, rồi lại đến Sửu. Ít người biết rằng vào mỗi năm Sửu, một cổng thời gian bí ẩn mở ra, cho phép bò đi tới bất kỳ năm Sửu nào khác trong quá khứ hoặc tương lai.

Bessie muốn dùng cổng thời gian mở trong năm nay để thăm \(N\) tổ tiên nổi tiếng từng sống từ lâu, với \(1\le N\le 0x10000\). Viết cận của \(N\) theo hệ thập lục phân rất hợp với năm Sửu; lưu ý 0x10000 bằng 65536.

Không may, du hành thời gian khiến Bessie hơi buồn nôn nên cô muốn thực hiện nhiều nhất \(K\) lần nhảy qua thời gian (\(1\le K\le N\)). Hãy tính số năm ít nhất để Bessie thăm tất cả tổ tiên rồi trở về năm hiện tại, với tổng cộng không quá \(K\) lần nhảy qua thời gian.

Bessie không bắt buộc dùng cổng trong một năm Sửu. Các cổng nối ngày đầu tiên của mọi năm Sửu với nhau; chẳng hạn, nếu Bessie đến một cổng rồi chờ 12 năm tới cổng tiếp theo, cô mất đúng 12 năm. Bessie bắt đầu vào ngày đầu tiên của năm Sửu hiện tại nên có thể lập tức đi ngược thời gian. Không tổ tiên nào của Bessie sống trong năm Sửu.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\). \(N\) dòng tiếp theo chứa \(N\) số nguyên phân biệt trong đoạn \(1\ldots10^9\), mỗi số cho biết một trong \(N\) tổ tiên của Bessie sống cách đây bao nhiêu năm.

Dữ liệu ra

In số năm ít nhất để Bessie thăm tất cả tổ tiên rồi trở về năm hiện tại.

Phân nhóm

Tất cả các test tuân theo các ràng buộc đã nêu.

Ví dụ

5 3
101
85
100
46
95

36

Nguồn

USACO 2021 February Contest, Silver - Year of the Cow: https://usaco.org/index.php?page=viewproblem2&cpid=1111

Tác giả: Brian Dean và David Yang.