Quelling Blade
Мистер Овца потерялся в компьютерной игре. В этой игре он выступает в роли супергероя, сражающегося со злом. Оборудование играет ключевую роль, и мистер Овца считает, что Quelling Blade — самое мощное оружие.
Каждый тип оружия в игре стоит денег и приносит выгоду герою. Если герой покупает два оружия (неважно, одного типа или разных), их выгоды суммируются. Например, если герой приобретает оружия с выгодой 3 и 5, он получит общую выгоду 8=3+5.
Для каждого оружия существуют определенные требования. Если герой хочет приобрести определенное оружие, ему могут понадобиться сначала другие оружия. Например, чтобы купить "Divine Rapier", нужны "Demon Edge" и "Scared Relic". Если он хочет второй "Divine Rapier", ему снова понадобятся "Demon Edge" и "Scared 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-битное целое число со знаком.