Problem description
Do pewnej znanej bajtockiej szkoły właśnie przyjechał fotograf robić zdjęcia klasowe. Z powodu elitarności tej szkoły istnieje możliwość, że nie wszyscy uczniowie zostaną sfotografowani mimo obecności.
Dokładniej, dyrektor wymaga ustawienia uczniów w R rzędów, po C uczniów w każdej. Chce, aby w każdym rzędzie byli uczniowie mniej więcej równego wzrostu. Dokładniej, zdefiniował on współczynnik nieporządku jako różnica pomiędzy wzrostem najwyższego i najniższego ucznia w danym rzędzie. Celem dyrekcji jest teraz zminimalizować maksimum współczynników nieporządku dla wszystkich rzędów.
Zadaniem fotografa jest wybrać i uporządkować uczniów do zdjęcia, aby spełnić wymogi dyrekcji. Niestety, fotograf nie jest zbyt dobry w takich zagadkach, dlatego to zadanie zlecił Tobie.
Napisz program, który wczyta liczbę obecnych uczniów, ich wzrosty oraz wartości R i C, wyznaczy optymalny wybór i ustawienie uczniów w rzędach i wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite: N, R i C, pooddzielane pojedynczymi odstępami i określające kolejno: liczbę obecnych uczniów, liczbę rzędów oraz liczbę kolumn, które należy sformować. W drugim i ostatnim wierszu wejścia znajduje się N liczb całkowitych Ai, pooddzielanych pojedynczymi odstępami. Są to wzrosty kolejnych uczniów wyrażone w bajtometrach.
Wyjście
W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba całkowita – maksymalny współczynnik nieporządku wszystkich rzędów dla optymalnego rozstawienia uczniów.
Ograniczenia
1 ≤ N ≤ 200 000, 1 ≤ R ⋅ C ≤ N, 1 ≤ Ai ≤ 109.
W testach wartych łącznie 50% maksymalnej punktacji: N ≤ 5 000.
Przykład
| Wejście | Wyjście | |
|
|