День іменинника#127

День іменинника

1 секунда
512 мегабайтів
Дуже легка

Під час проведення І Всеукраїнської Зимової Комп'ютерної школи було вирішено відсвяткувати — «День іменинника». K учасників святкували свій день народження, а інші N вирішили зробити іменинникам солодкий сюрприз і принесли кожен по шоколадці і віддали їх старшій вожатій Марині (усі знають що, для Марини головне — чесність), щоб вона поділила їх між іменинниками.

Марина хоче роздати шоколадки іменинникам так, щоб у кожного з них був однаковий набір шоколадок: однакова кількість молочних шоколадок, шоколадок з ізюмом, чорного шоколаду і інших. Може вийти так, що усі шоколадки порівну розділити не вийде. У цьому випадку їх можна буде використовувати в якості призів на конкурсах.

Марина хоче роздати якомога більше шоколадок іменинникам, проте вона зайнята підготовкою конкурсів. Вона просить Вас визначити оптимальний набір шоколадок, який отримає кожен з K іменинників.

Вхідні дані

Перший рядок вхідного файлу містить два числа (1 \le N, K \le 10^5) — кількість шоколадок і кількість іменинників відповідно. Другий рядок вхідного файлу містить цілих чисел a_i (1 \le a_i \le 100) — кількість шоколадок кожного типу.

Вихідні дані

Перший рядок вихідного файлу має містити число — максимальна кількість шоколадок, яку зможе отримати кожен іменинник. Другий рядок повинен містити цілих чисел b_i — типи шоколадок (з урахуванням кількості), які отримає кожен іменинник. Дана послідовність має бути виведена в порядку неспадання.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

Маючи 4 шоколадки першого типу і 3 другого типу, обидва іменинника отримають по дві шоколадки першого типу і по одній другого.

Усі шоколадки будуть використані в якості призів.

Оцінювання

N \le 100, для усіх : a_i = 1 — не менше 20 балів

N \le 100, для усіх : a_i \le 2 — не менше 40 балів

N \le 5000 — не менше 75 балів