Quelling Blade
Пан Вівця загубився в комп'ютерній грі. У цій грі він виступає в ролі супергероя, який бореться зі злом. Обладнання відіграє важливу роль, і пан Вівця вважає, що Quelling Blade — це наймогутніша зброя.
У грі кожен вид зброї має свою вартість і приносить певну вигоду. Якщо герой купує дві одиниці зброї (незалежно від того, чи однакового вони типу), вигоди від них додаються. Наприклад, якщо герой купує зброю з вигодою 3 і 5, загальна вигода становитиме 8=3+5.
Кожна зброя має свої вимоги. Якщо герой хоче купити певну зброю, йому можуть знадобитися інші види зброї спочатку. Наприклад, для придбання "Divine Rapier" потрібні "Demon Edge" і "Sacred Relic". Звісно, якщо він хоче купити другий "Divine Rapier", йому знову знадобляться "Demon Edge" і "Sacred Relic". Зверніть увагу, що наявна зброя не зникає після покупки. Також можливо, що для однієї зброї потрібно кілька одиниць іншої. Ви можете припустити, що один тип зброї потрібен не більше ніж для одного іншого типу.
Герой зайнятий боєм і не має часу заробляти гроші. На щастя, гра надає герою 1 монету за секунду. Тому, якщо герой хоче купити "Quelling Blade", мінімальний час для досягнення цієї мети можна легко обчислити.
Пан Вівця — перфекціоніст. Він не лише хоче отримати "Quelling Blade" якомога швидше, але й прагне оптимізувати кожну секунду гри. Він визначає корисність гри як суму вигоди героя за кожну секунду. Він обчислює корисність від початку гри до моменту, коли він отримує "Quelling Blade", виключно. Ви можете звернутися до прикладів для подальшого пояснення. Іншими словами, ви повинні знайти спосіб купівлі зброї, який мінімізує час для отримання "Quelling Blade" і оптимізує корисність гри.
Вхідні дані
Є кілька сотень тестових випадків, кількість яких вказана в першому рядку введення. Зверніть увагу, що більшість тестових випадків відносно невеликі.
Для кожного тестового випадку перший рядок містить одне ціле число N, що позначає кількість різних типів зброї. (1 ≤ N ≤ 1000)
Наступні рядки описують зброю. Для кожного виду зброї перший рядок містить два цілі числа B і C, що позначають вигоду і вартість цього виду зброї. (1 ≤ B, C ≤ 2^31-1) Потім одне ціле число P в наступному рядку описує кількість вимог для цієї зброї. Наступні P рядків, кожен з яких містить два цілі числа I і A, означають, що ця зброя потребує A одиниць зброї з індексом I.
Індекси зброї починаються з 1 до N. "Quelling Blade" — це перший тип зброї. Ви можете припустити, що загальна кількість зброї, необхідної для "Quelling Blade", менше 1000000. Також зверніть увагу, що "Quelling Blade" можна придбати за кінцевий ігровий час, і один тип зброї може бути потрібен не більше ніж для одного іншого типу зброї.
Вихідні дані
Для кожного тестового випадку виведіть одне ціле число, що позначає оптимальну корисність. Ви можете припустити, що відповідь вміщується в 64-бітне знакове ціле число.