Управління Водними Воротами
У дамби є n водозливів, які можуть випускати воду за потреби. Кожен водозлив має свою пропускну здатність, водний шлях і зони, що зазнають впливу нижче за течією. Ці зони можуть бути під загрозою затоплення, коли водозлив відкритий. Вартість потенційних збитків, завданих водозливом, визначається числом, яке розраховується з кількості людей та зон, що можуть постраждати.
Припустимо, що водозлив G_i має об'ємну витрату F_i м^3/год і вартість збитків C_i. У певній ситуації дамба має об'єм V м^{3} води, який потрібно скинути протягом T годин. Ваше завдання — керувати відкриттям водозливів так, щоб позбутися принаймні зазначеного об'єму води за обмежений час, при цьому мінімізуючи вартість збитків.
Наприклад, у дамби є 4 водозливи, і їхні властивості наведені в таблиці нижче.
Випадок 1: Ви повинні скинути воду об'ємом 5 мільйонів м^{3} протягом 7 годин. Мінімальна вартість буде 120,000, якщо відкрити водозлив G_1 на 7 годин.
Випадок 2: Ви повинні скинути воду об'ємом 5 мільйонів м^{3} протягом 30 годин. Мінімальна вартість буде 110,000, якщо відкрити водозливи G_2 та G_3, наприклад, G_2 відкритий на 29 годин, а G_3 відкритий на 28 годин.
Зверніть увагу, що кожен водозлив є незалежним і може бути відкритий лише на цілу кількість годин (без дробових годин).
Вхідні дані
Перша строка містить ціле число n, що вказує кількість водозливів (1 ≤ n ≤ 20). Далі йдуть n рядків, кожен з яких містить два цілі числа: F_i та C_i, що відповідають витраті (м^3/год) та вартості збитків водозливу G_i відповідно. Наступний рядок містить число m, яке є кількістю тестових випадків (1 ≤ m ≤ 50). Наступні m рядків містять, у кожному рядку, два цілі числа: V та T, що відповідають об'єму (м^3) води, яку потрібно скинути протягом T годин.
1 ≤ F_i, V, C_i ≤ 10^9, 1 ≤ T ≤ 1000
Вихідні дані
Для кожного тестового випадку виведіть мінімальну вартість у точному форматі, показаному в прикладі виходу нижче. Якщо неможливо скинути воду об'ємом V за T годин з дамби, виведіть "IMPOSSIBLE" (без лапок).