Biuro podróży

Limit pamięci: 32 MB

W ostatnim czasie mieszkańcy Bajtocji zaczęli podróżować częściej niż dotychczas. Przedsiębiorczy Bajtazar wpadł na pomysł otwarcia biura podróży. Już pierwszego dnia urzędowania do biura zgłosiło się klientów (na potrzeby naszego zadania możemy ich ponumerować liczbami naturalnymi od do ), którzy chcą pojechać na wycieczkę. Niestety każdy z nich ma swoje wymagania.

Twoim zadaniem jest pomóc Bajtazarowi w wybraniu klientów, którzy pojadą na wycieczkę, tak aby zmaksymalizować zysk Bajtazara.

Każdy klient określił, ile wynosi dla niego wartość wycieczki organizowanej przez Bajtazara. Niech będzie taką wartością dla klienta (). Jeśli , to klient zapłaci bajtockich dolarów, aby pojechać na wycieczkę, jeśli natomiast , to aby klient pojechał na wycieczkę, Bajtazar musi mu dopłacić bajtockich dolarów.

Klienci oprócz wymagań finansowych posiadają również wymagania towarzyskie. Klient ma () takich wymagań, -te wymaganie -tego klienta jest reprezentowane przez parę liczb całkowitych () (). Wymaganie to należy rozumieć tak, że aby klient pojechał na wycieczkę, to na wycieczkę musi pojechać również klient lub koszt wycieczki dla klienta musi zostać obniżony o bajtockich dolarów (może się zdarzyć, że koszt wycieczki dla pewnych klientów z dodatniego stanie się ujemny, co spowoduje, że Bajtazar będzie musiał dopłacić tym klientom, żeby wzięli oni udział w wycieczce, rekompensując tym samym brak zaspokojenia ich wymagań towarzyskich).

Pomóż Bajtazarowi wybrać grupę klientów, których ma zabrać na wycieczkę, tak aby zmaksymalizować jego zysk (liczba miejsc na wycieczce jest nieograniczona).

Zadanie

Dysponujesz jedenastoma zestawami danych, które możesz ściągnąć stąd. Każdy zestaw jest zapisany w osobnym pliku biu.in, gdzie to numer zestawu (). Rozwiązaniem zadania powinien być program, który wczytuje ze standardowego wejścia jedną liczbę całkowitą , i wypisuje na standardowe wyjście odpowiedź dla -tego zestawu. Rozwiązanie zestawu biu0.in nie jest punktowane.

W pierwszym wierszu odpowiedzi powinna się znajdować dokładnie jedna liczba całkowita () - liczba klientów, których Bajtazar powinien zabrać na wycieczkę. Jeśli liczba jest dodatnia, w drugim wierszu powinno się znaleźć liczb całkowitych, oddzielonych pojedynczymi odstępami, będących numerami klientów, których Bajtazar powinien zabrać na wycieczkę. Jeśli istnieje wiele optymalnych rozwiązań to możesz podać dowolne z nich. Numery klientów mogą być umieszczone w wyjściu w dowolnej kolejności.

Opis pojedynczego pliku wejściowego

W pierwszym wierszu znajduje się dokładnie jedna liczba całkowita () oznaczająca liczbę klientów biura podróży. W kolejnych wierszach opisani są poszczególni klienci. W -wszym wierszu () znajdują się liczby całkowite () oraz (), a za nimi par liczb całkowitych , () - wszystkie liczby w wierszu oddzielone są pojedynczymi odstępami. Możesz założyć, że każdy klient ma co najwyżej jedno wymaganie towarzyskie dotyczące dowolnego innego klienta.

Przykład

4
5 0
6 2 1 10 3 1
-10 0
1 2 1 10 2 10

3
1 2 4

Jeśli Bajtazar wybierze klientów , to osiągnie zysk bajtockich dolarów, co jest rozwiązaniem optymalnym.

Autor zadania: Marek Cygan.