Уважаемые математики, информатики и просто неравнодушные граждане)). Застряли с ребёнком над задачей про грузовик. Вдруг кто-то захочет мимо проходя углубиться)). Заранее бескрайняя благодарность. Итак:
Петя собирается купить грузовичок и заняться перевозками. Он изучил рынок и выяснил, что в
его городе есть n потенциальных клиентов. Для i-го клиента есть mi вариантов контракта. Каждый
вариант задается двумя числами: wij — минимальная грузоподъемность грузовика, которая необходима, чтобы выполнить контракт, и cij — прибыль, которую получит Петя, если заключит этот
контракт. С каждым клиентом можно заключить не более одного контракта.
Сейчас Петя думает, какой грузовик лучше купить, чтобы получить нужную ему прибыль. У
него есть q вариантов. В i-м варианте Петя хочет, чтобы его прибыль была не меньше xi
. Помогите
ему для каждого из вариантов найти минимальную грузоподъемность грузовика, с которой можно
получить такую прибыль.
Формат входных данных
Первая строка содержит число n (1 <= n <= 105).
Далее следуют n блоков, описывающих варианты контракта для каждого из потенциальных
клиентов. Каждый такой блок начинается с числа mi
, далее следуют mi пар чисел wij , cij
Далее следует число q (1 <= q <= 105). Далее следуют q чисел xi (1 <= xi <= 109).
Формат выходных данных
Выведите q чисел — минимальную грузоподъемность грузовика, с которой можно получить требуемую прибыль, для каждого из вариантов. Если требуемую прибыль получить невозможно, выведите −1 для соответствующего варианта.
Пример во вложении. Тока не пишите пожалуйста "эта задача решается элементарным методом таким-то", имейте снисхождение)) если нужно по-русски перевести условия задачи, я переведу))