Pakowanie kontenerów

Limit pamięci: 32 MB

Pewna fabryka pakuje swoje wyroby do pudełek, które mają kształt walca. Podstawy wszystkich pudełek są takie same. Wysokość każdego pudełka jest zawsze nieujemną, całkowitą potęgą dwójki, tzn. liczbą postaci , dla pewnego . Liczbę (wykładnik potęgi), która charakteryzuje wielkość pudełka, nazywamy rozmiarem tego pudełka. We wszystkich pudełkach znajduje się taki sam towar, ale w różnych pudełkach wartość towaru może być różna — towar wyprodukowany wcześniej jest tańszy. Dyrekcja fabryki wydała zarządzenie, żeby starać się wydawać najpierw towar najstarszy, czyli o najmniejszej wartości. Towar jest wywożony z magazynu w kontenerach. Każdy kontener, podobnie jak pudełka, ma kształt walca. Średnica kontenera jest niewiele większa od średnicy pudełek tak, że pudełka można swobodnie umieszczać w kontenerach. Wysokość każdego kontenera jest też nieujemną, całkowitą potęgą dwójki. Podobnie jak w przypadku pudełek, rozmiarem kontenera nazywamy wykładnik tej potęgi. Żeby bezpiecznie przewozić towar w kontenerze, należy go szczelnie wypełnić pudełkami, tzn. suma wysokości umieszczonych w kontenerze pudełek musi być równa wysokości tego kontenera.

Do magazynu dostarczono zestaw kontenerów. Sprawdź, czy można pudełkami z magazynu wypełnić szczelnie wszystkie kontenery. Jeśli tak, to podaj minimalną wartość towaru jaki można wywieźć z magazynu w tych, szczelnie wypełnionych, kontenerach.

Przykład

Rozważmy magazyn, w którym znajduje się pudełek o następujących rozmiarach i wartościach przechowywanego w nich towaru:

1 3
1 2
3 5
2 1
1 4

Dwa kontenery o rozmiarach i można szczelnie wypełnić dwoma pudełkami o łącznej wartości , lub , lub trzema pudełkami o łącznej wartości . Kontener o rozmiarze nie da się szczelnie wypełnić pudełkami z magazynu.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia charakterystyki pudełek w magazynie (rozmiar, wartość) oraz charakterystyki kontenerów (ile jest kontenerów danego rozmiaru);
• sprawdza, czy wszystkie kontenery w zestawie można szczelnie wypełnić pudełkami z magazynu, a jeśli tak, to oblicza minimalną wartość towaru jaką można w tych kontenerach wywieźć z magazynu;
• zapisuje wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita , . Jest to liczba pudełek w magazynie. W każdym z kolejnych wierszy zapisane są dwie nieujemne liczby całkowite oddzielone pojedynczym odstępem. Są to charakterystyki jednego pudełka, odpowiednio, rozmiar pudełka i wartość zawartego w nim towaru. Rozmiar pudełka jest nie większy od , natomiast wartość jest nie większa od .

W kolejnym wierszu podana jest dodatnia liczba całkowita określająca, ile różnych rozmiarów mają kontenery dostarczone do magazynu. W każdym z kolejnych wierszy jest zapisana para dodatnich liczb całkowitych oddzielonych pojedynczym odstępem. Pierwsza z tych liczb jest rozmiarem kontenera, natomiast druga jest liczbą dostarczonych kontenerów o tym rozmiarze. Wiadomo, że maksymalna liczba kontenerów nie przekracza , a rozmiar kontenera jest nie większy od .

Wyjście

Twój program powinien zapisać w pierwszym i jedynym wierszu standardowego wyjścia:

• jedno słowo NIE, jeżeli nie da się szczelnie wypełnić pudełkami z magazynu kontenerów z podanego zestawu, lub
• jedną liczbę całkowitą, której wartość jest równa minimalnej, łącznej wartości towaru z pudełek, którymi można szczelnie wypełnić wszystkie kontenery z podanego zestawu.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

3

Autor zadania: Wojciech Rytter.