Banki

Limit pamięci: 32 MB

Do bajtockich banków często przybywają kupcy, chcący wypłacić pieniądze ze swoich kont. W każdym banku dostępne są tylko dwa nominały, ale każdego z nich jest nieograniczona liczba. Nie każdą kwotę da się wypłacić, więc banki wywieszają listy, informujące klientów o niedostępnych sumach. Czasami listy te są tak długie, że banki wywieszają tylko początkową część niewypłacalnych kwot.

Kupiec Kozik chce wypłacić dużą kwotę pieniędzy. Zanim wyruszy do banku, to chciałby znać najwyższe kwoty, których banki nie są w stanie wypłacać. Kozik nie ma dostępu do list wywieszonych przez banki. Ma jedynie informację o dostępnych nominałach.

Wejście

Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę bajtockich banków. W następnych wierszach znajdują się opisy banków. Każdy wiersz zawiera dwie liczby całkowite (), oznaczające wartości dostępnych nominałów.

W testach wartych około punktów zachodzą dodatkowe warunki: i .

Wyjście

Standardowe wyjście powinno zawierać wierszy, będące odpowiedziami dla kolejnych banków. W każdym wierszu powinna znaleźć się jedna liczba całkowita, równa najwyższej kwocie, której bank nie może wypłacić, lub wartość -1, jeśli takiej kwoty nie można ustalić.

Przykład

Dla danych wejściowych:

3
2 5
3 8
5 10

poprawną odpowiedzią jest:

3
13
-1

Autor zadania: Joanna Bujnowska, Jacek Tomasiewicz.