Zatrudnianie

Limit pamięci: 64 MB

Chcesz zatrudnić robotników do pewnego projektu budowlanego. Do pracy zaaplikowało kandydatów, ponumerowanych od do . Jeśli kandydat zostanie zatrudniony, trzeba mu zapłacić co najmniej dolarów. Ponadto, każdy kandydat posiada poziom kwalifikacji . Prawo budowlane wymaga, żebyś płacił swoim robotnikom proporcjonalnie do ich poziomu kwalifikacji, relatywnie względem wszystkich pozostałych. Na przykład, jeżeli zatrudnisz dwóch robotników i oraz , to będziesz musiał zapłacić robotnikowi dokładnie trzy razy więcej niż robotnikowi . Wypłaty robotników mogą być niecałkowite. Uwzględniamy na\-wet liczby, których nie można zapisać za pomocą skończonej liczby cyfr w postaci dziesiętnej, takie jak jedna trzecia czy jedna szósta dolara.

Dysponujesz dolarami i chcesz zatrudnić tak wielu robotników, jak tylko się da. Ty decydujesz o tym, kogo zatrudnisz i ile komu zapłacisz, ale musisz spełnić wymagania dotyczące minimalnych wypłat tych, których zatrudnisz, i musisz przestrzegać przepisów budowlanych. Ponadto musisz zmieścić się w budżecie dolarów.

W twoim projekcie poziomy kwalifikacji zupełnie nie grają roli, więc jesteś zainteresowany wyłącznie maksymalizacją liczby zatrudnionych robotników, niezależnie od ich poziomów kwalifikacji. Jednakże, jeśli istnieje więcej niż jeden sposób osiągnięcia tego celu, chciałbyś wy\-brać taki sposób, w którym łączna ilość pieniędzy, które musisz zapłacić robotnikom, jest najmniejsza możliwa. Jeżeli istnieje wiele sposobów osiągnięcia tego celu, to wszystkie one są dla ciebie równie dobre i zadowolisz się dowolnym z nich.

Zadanie

Napisz program, który mając dane wymagania dotyczące wypłat oraz poziomów kwalifikacji robotników, a także ilość pieniędzy będących w twoim posiadaniu, wyznaczy, których kandydatów powinieneś zatrudnić. Powinieneś zatrudnić tak wielu z nich, jak tylko się da, a ponadto zrealizować to za pomocą najmniejszej możliwej ilości pieniędzy, nie przekraczając opisanego powyżej prawa budowlanego.

Ograniczenia

- liczba kandydatów
- wymagana przez kandydata pensja minimalna
- poziom kwalifikacji kandydata
- ilość pieniędzy, którymi dysponujesz

Ważna uwaga

Maksymalna wartość parametru nie mieści się w 32 bitach. Powinieneś użyć 64-bitowego typu danych, takiego jak typ long long w C/C++ czy int64 w Pascalu, żeby przechowywać wartość w jednej zmiennej.

Wejście

Twój program powinien wczytać ze standardowego wejścia następujące dane:

• Pierwszy wiersz zawiera liczby całkowite oraz , oddzielone pojedynczym odstępem.
• Kolejne wierszy zawiera opisy kandydatów, po jednym w wierszu. -ty z tych wierszy opisuje kandydata numer i zawiera liczby całkowite oraz , oddzielone pojedynczym odstępem.

Wyjście

Twój program powinien wypisać na standardowe wyjście następujące dane:

• Pierwszy wiersz powinien zawierać jedną liczbę całkowitą - liczbę robotników, których zatrudnisz.
• Kolejne wierszy powinno zawierać numery identyfikacyjne kandydatów, których postanowiłeś zatrudnić (każdy z nich powinien być inną liczbą z zakresu od do ), po jednym w wierszu, w dowolnej kolejności.

Ocenianie

W każdym z testów uzyskasz pełną punktację, jeżeli twój wybór kandydatów osiągnie wszystkie cele i spełni wszystkie wymagania. Jeżeli stworzysz plik wyjściowy, w którym pierwszy wiersz będzie poprawny (tzn. z poprawną wartością parametru ), ale który nie spełnia powyższego opisu, uzyskasz 50% punktów za ten test. Stanie się tak nawet w przypadku, gdy wyjście nie będzie poprawnie sformatowane, o ile tylko pierwszy wiersz będzie poprawny.

W testach wartych łącznie 50 punktów nie przekroczy .

Przykład

Dla danych wejściowych:

4 100
5 1000
10 100
8 10
20 1

poprawną odpowiedzią jest:

2
2
3

Wyjaśnienie do przykładu: Jedynym sposobem na to, żeby było cię stać na zatrudnienie dwóch robotników i żeby wciąż spełnić wszystkie wymagania, jest wybranie robotników o numerach 2 i 3. Możesz zapłacić im odpowiednio 80 i 8 dolarów i w ten sposób zmieścisz się w budżecie równym 100.

Dla danych wejściowych:

3 4
1 2
1 3
1 3

poprawną odpowiedzią jest:

3
1
2
3

Wyjaśnienie do przykładu: W tym przypadku stać cię na zatrudnienie wszystkich robotników. Zapłacisz 1 dolara robotnikowi 1 i 1,50 dolara każdemu z robotników 2 i 3, i w ten sposób zdołasz zatrudnić wszystkich, używając posiadanych przez ciebie 4 dolarów.

Dla danych wejściowych:

3 40
10 1
10 2
10 3

poprawną odpowiedzią jest:

2
2
3

Wyjaśnienie do przykładu: W tym przypadku nie stać cię na zatrudnienie wszystkich robotników, gdyż kosztowałoby cię to 60 dolarów, lecz możesz zatrudnić dowolnych dwóch. Postanawiasz zatrudnić robotników 2 i 3, ponieważ kosztuje cię to najmniej pieniędzy w porównaniu do pozostałych kombinacji złożonych z par robotników. Możesz zapłacić 10 dolarów robotnikowi 2 i 15 dolarów robotnikowi 3, wydając łącznie 25 dolarów. Gdybyś zatrudnił robotników 1 i 2, musiałbyś im zapłacić odpowiednio co najmniej 10 i 20 dolarów. Gdybyś zatrudnił robotników 1 i 3, musiałbyś im zapłacić odpowiednio co najmniej 10 i 30 dolarów.