VIII Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 29.05.2004

Opis

Firma castingowa Moviestar organizuje casting do superprodukcji filmowej "The Battle of Endor". Do filmu potrzebnych jest wiele tysięcy statystów. Firma rozesłała zaproszenia na rozmowę do wielu aktorów, chcąc porozmawiać z każdym z nich, w celu sprawdzenia ich kwalifikacji. Ponieważ nie było wiadomo ilu aktorów się stawi, firma ustaliła termin i miejsce rozmowy identyczne dla wszystkich.

Tuż przed spotkaniem firma przeanalizowała doświadczenie zawodowe każdego kandydata, do którego wysłała zaproszenie i wstępnie oszacowała czas rozmowy, jaki będzie potrzebny do oceny przydatności każdego kandydata. Ponadto firma zdecydowała się pokryć koszty czasu oczekiwania każdego kandydata, wypłacając mu rekompensatę za udział w castingu. W celu obliczenia tej rekompensaty firma, kierując się pozycją każdego kandydata w branży, przyjęła pewną podstawową stawkę na jednostkę czasu oraz przelicznik (dodatnia liczba całkowita), rosnący w zależności od doświadczenia zawodowego kandydata (1 to kandydat bez doświadczenia). Wypłacona kandydatowi rekompensata jest iloczynem jego przelicznika i czasem poświęconym przez kandydata na udział w castingu (tzn. sumę czasu oczekiwania i czasu rozmowy). Firma, obawiając się dużego zainteresowania ze strony kandydatów i dużej grupy oczekujących, zastanawia się w jakiej kolejności wywoływać kandydatów, aby sumaryczny koszt wszystkich rekompensat był minimalny.

Zadanie

Dla danej liczby kandydatów, którzy zgłosili się na casting, z których każdy jest scharakteryzowany przez szacowany czas rozmowy i stopień doświadczenia zawodowego, należy określić kolejność wywoływania kandydatów na rozmowę, która minimalizuje sumaryczną wartość rekompensat wypłaconych przez firmę.

Specyfikacja wejścia

W pierwszym wierszu wejścia znajduje się jedna dodatnia liczba całkowita D (D ≤ 50), oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. Każdy zestaw ma następującą postać. W pierwszym wierszu znajduje się jedna liczba całkowita N (1 ≤ N ≤ 30.000), oznaczająca liczbę kandydatów, którzy stawili się na casting. W kolejnych dwóch wierszach zestawu znajduje się po N dodatnich liczb całkowitych. W pierwszym z nich znajdują się szacowane czasy rozmowy dla kolejnych kandydatów (kandydaci numerowani są od 1 do N); są to liczby z przedziału [1; 10.000]. W drugim znajdują się przeliczniki (od 1 do 10.000) przyjęte dla kolejnych kandydatów.

Specyfikacja wyjścia

Dla każdego zestawu danych pojawiającego się na wejściu należy wypisać wiersz zawierający kolejność wywoływania kandydatów na rozmowę (tzn. ciąg numerów kandydatów, oddzielonych spacjami). Jeśli kolejność w pewnej podgrupie kandydatów nie jest istotna, kandydaci powinni być wywoływani według rosnących numerów.

Przykład

3
2
5 10
1 1
2
5 10
1 5
3
2 3 2
2 4 2

1 2
2 1
2 1 3