C. Qalamlar to‘plami

Litseyning rasm to‘garagida N ta rangli qalam bor. Ranglar 1 dan K gacha raqamlangan, i-qalamning rangi cᵢ.

To‘garak rahbari qalamlardan to‘plamlar yig‘moqchi: har bir to‘plamda K ta rangning har biridan aynan bittadan qalam bo‘lishi kerak. Har bir qalam ko‘pi bilan bitta to‘plamga kiradi.

Eng ko‘pi bilan nechta to‘plam yig‘ish mumkin? Shunda nechta qalam hech qaysi to‘plamga kirmay qoladi?

Kirish ma’lumotlari

Birinchi qatorda ikkita butun son N va K — qalamlar va ranglar soni.

Ikkinchi qatorda N ta butun son c₁, c₂, …, cₙ — qalamlarning ranglari.

Chiqish ma’lumotlari

Bitta qatorda bo‘sh joy bilan ajratilgan ikkita butun son — to‘plamlarning eng ko‘p soni va ortib qolgan qalamlar soni.

Cheklovlar

• 1 ≤ N, K ≤ 2·10⁵
• 1 ≤ cᵢ ≤ K

1-misol: 1-rangdan 3 ta, 2-rangdan 2 ta, 3-rangdan 3 ta qalam. 2-rangli qalam faqat 2 ta, shuning uchun 2 ta to‘plam yig‘iladi — 6 ta qalam ketadi, 2 tasi qoladi.

2-misol: 3-rangli qalam umuman yo‘q — bitta ham to‘plam yig‘ib bo‘lmaydi, 4 ta qalamning hammasi qoladi.