Superkomputer

Limit pamięci: 256 MB

Bajtazar stworzył superkomputer o bardzo nowatorskiej konstrukcji. Może on zawierać wiele (takich samych) procesorów. Każdy procesor może w jednostce czasu wykonać jedną instrukcję.

Programy nie są w tym komputerze wykonywane sekwencyjnie, lecz mają strukturę drzewa. Każda instrukcja programu może mieć zero, jedną lub wiele instrukcji następujących po niej. Po wykonaniu każdej instrukcji należy wykonać instrukcje następujące po niej, jednak można je wykonać w dowolnej kolejności; w szczególności można je wykonywać równolegle na różnych procesorach. Jeśli w superkomputerze jest procesorów, to w każdej jednostce czasu będzie można wykonać równolegle co najwyżej instrukcji.

Bajtazar ma do uruchomienia pewien program. Ponieważ chce optymalnie wykorzystywać swoje zasoby, zastanawia się, jak liczba procesorów wpłynie na szybkość obliczeń. Prosi Cię o określenie, dla danego programu i liczby procesorów, najkrótszego możliwego czasu wykonania tego programu z użyciem superkomputera o tylu procesorach.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i () oddzielone pojedynczym odstępem, oznaczające liczbę instrukcji programu Bajtazara oraz liczbę zapytań.

W drugim wierszu wejścia znajduje się ciąg liczb całkowitych () pooddzielanych pojedynczymi odstępami: oznacza liczbę procesorów, którymi dysponuje Bajtazar w -tym zapytaniu.

W trzecim i ostatnim wierszu wejścia znajduje się ciąg liczb całkowitych () pooddzielanych pojedynczymi odstępami: określa numer instrukcji, po której następuje instrukcja numer . Instrukcje numerowane są kolejnymi liczbami naturalnymi od 1 do , przy czym instrukcja numer 1 to pierwsza instrukcja programu.

W testach wartych łącznie 35% punktów zachodzi dodatkowo warunek: , . W podzbiorze tych testów wartym łącznie 20% punktów zachodzi dodatkowo warunek: , .

Wyjście

Twój program powinien wypisać na standardowe wyjście jeden wiersz zawierający ciąg liczb całkowitych pooddzielanych pojedynczymi odstępami: -ta z tych liczb powinna określać minimalny czas wykonania programu przy założeniu, że superkomputer Bajtazara posiada procesorów.

Przykład

Dla danych wejściowych:

20 1
3
1 1 1 3 4 3 2 8 6 9 10 12 12 13 14 11 11 11 11

poprawną odpowiedzią jest:

8

Wyjaśnienie do przykładu:

Wykonanie programu może wyglądać następująco:

Testy "ocen":

• 1ocen: , , drzewo instrukcji jest ścieżką;
• 2ocen: , , mały losowy test;
• 3ocen: , , wszystkie instrukcje następują po instrukcji nr ;
• 4ocen: , , instrukcje tworzą pełne drzewo binarne;
• 5ocen: , , drzewo instrukcji jest długą ścieżką.

Autor zadania: Michał Włodarczyk.