Problem description

Back
Show PDF
Podział na grupy
(B)
Limit pamięci: 512 MB
Limit czasu: 2.00 s

test test

A kto nie trafi do żadnej z grup to zmarznie.

Ach tak, to właśnie początek kolejnego obozu informatycznego przygotowującego spragnionych wiedzy licealistów do Olimpiady Informatycznej. Tym razem odbywa się on w miejscowości Lewin Kłodzki i otacza go zimowa aura napędzana grudniowym, zimnym górskim powietrzem.

Na obozach zwykle bywało tak, że gdy tylko zaczynały się, to Kadra miała w zwyczaju od razu wpadać w rozmaite tarapaty. Tak stało się i tym razem – Kadra nie za bardzo potrafi sobie poradzić z podzieleniem uczestników obozu na odpowiednie grupy.

Na obóz przyjechało N uczestników, każdemu z nich Kadra przypisała poziom umiejętności Ai, zgodnie z liczbą wbitych do tej pory zadanek na serwisie Solve. Uczestników obozu należy podzielić na K grup, w taki sposób, aby różnica poziomu umiejętności dowolnych dwóch uczestników obozu z tej samej grupy różniła się o nie więcej niż D. Niestety liczba grup K jest ograniczona przez liczbę sal na terenie ośrodka, a liczba D jest uwarunkowana wybranymi na obóz zadaniami, może się więc okazać, że nie wszystkich uczestników obozu uda się przypisać do jakiejkolwiek grupy. I tutaj właśnie pojawia się problem Kadry: chcieliby podzielić uczestników na grupy w taki sposób, aby jak najwięcej z nich trafiło do jakiejkolwiek grupy.

Twoim zadaniem będzie napisanie programu, który na podstawie listy poziomów umiejętności uczestników, maksymalnej liczby grup i maksymalnej różnicy poziomów umiejętności wyznaczy maksymalną liczbę osób, które można podzielić na grupy.

Wejście

W pierwszym wierszu wejścia znajduje się trzy liczby naturalne N, D i K, pooddzielane pojedynczymi odstępami i oznaczające odpowiednio liczbę uczestników obozu, maksymalną różnicę poziomów umiejętności oraz maksymalną liczbę grup. W drugim wierszu wejścia znajduje się ciąg N liczb naturalnych Ai, pooddzielanych pojedynczymi odstępami i oznaczającymi poziomy umiejętności kolejnych uczestników.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba naturalna – maksymalna liczba uczestników, którą można podzielić na grupy zgodnie z zasadami opisanymi w treści zadania.

Ograniczenia

1 ≤ N ≤ 500 000, 1 ≤ D, Ai ≤ 109, 1 ≤ K ≤ 10.

Podzadanie Warunki Punkty
1 K = 1 20
2 K = 2 20
3 N ≤ 20, K ≤ 5 20
4 N ≤ 1000 20
5 brak dodatkowych ograniczeń 20

Przykład

Wejście Wyjście Wyjaśnienie 
5 1 2
6 1 2 4 6

4

Uczestnicy z poziomami umiejętności 1 i 2 mogą być w jednej grupie, a dwójka uczestników z poziomami umiejętności 6 w drugiej grupie.
Wejście Wyjście Wyjaśnienie 
2 2 3
3 1

2

Uczestnicy mogą być razem w grupie, a dwie mogą zostać niewykorzystane.
Wejście Wyjście Wyjaśnienie 
5 1 2
6 1 2 3 6

4

Uczestnicy z poziomami umiejętności 2 i 3 mogą być w jednej grupie, a dwójka uczestników z poziomami umiejętności 6 w drugiej grupie.