
MEETING	Встреча MEETING Теория Несколько друзей решили отпраздновать победу на командной олимпиаде школьников. Но в связи с повышением цен на билеты возникла следующая проблема: все они живут в разных частях города, поэтому им нужно выбрать место встречи так, чтобы на поездки не пришлось тратить слишком много денег (хоть немного должно остаться на праздник). Вы должны помочь им сделать наилучший выбор. Пусть остановки пронумерованы натуральными числами от 1 до N включительно, а в городе ходит M маршрутов трамвая (все друзья ездят исключительно на трамваях и не ходят пешком между остановками). Для каждого маршрута известны номера составляющих его остановок. Пусть встретиться собираются K человек, и известно у кого сколько денег и есть ли проездной на трамвай. Цену билета считать равной 4 условным единицам. Задача Вам требуется найти номер такой остановки, чтобы все могли доехать до неё, и сумма денег, потраченных ими на проезд была минимальной. Естественно, можно делать пересадки с маршрута на маршрут, но учтите, что каждый раз, делая пересадку, требуется покупать новый билет: друзья зайцами не ездят. За дорогу до места встречи каждый платит сам. Денег на обратную дорогу оставлять не требуется. Технические требования: Входной файл: INPUT.TXT Выходной файл: OUTPUT.TXT Ограничение по времени тестирования: до 5 секунд на один тест Входной файл: в первой строке даны два натуральных числа N и M, (N<=100 - количество остановок и M<=100 - количество маршрутов). В следующих M строках идёт описание маршрутов трамвая следующим образом: в начале строки находится натуральное число L<=100, задающее число остановок в маршруте. Затем идут L натуральных чисел, задающих номера остановок в маршруте. Все числа в строке разделены пробелами. Затем следует строка с натуральным числом K<=100 (K - количество человек). В следующих K строках информация для каждого из них, по строке на человека. В начале строки указано целое неотрицательное число, задающее количество денег (в условных единицах) у человека. Затем номер остановки, до которой он доходит от дома пешком, за ним следует либо число 0 (если этот человек не имеет проездного), либо 1 (если имеет). Числа в строке разделены пробелами. Никто из друзей не имеет больше 1000 условных единиц. Выходной файл: вы должны вывести два числа: номер остановки, на которой друзья должны встретиться (если таких номеров несколько выведите наименьший) и суммарное количество денег (в условных единицах), затраченное на поездки друзьями. Числа должны быть разделены пробелом. Если друзья не смогут все встретиться на одной остановке, то вы должны вывести единственное число 0. Пример: INPUT.TXT 4 3 2 1 2 2 2 3 2 3 4 3 27 1 0 15 4 0 45 4 0 OUTPUT.TXT 4 12

MEETING

Встреча
MEETING

Теория
Несколько друзей решили отпраздновать победу на командной олимпиаде школьников. Но в связи с повышением цен на билеты возникла следующая проблема: все они живут в разных частях города, поэтому им нужно выбрать место встречи так, чтобы на поездки не пришлось тратить слишком много денег (хоть немного должно остаться на праздник). Вы должны помочь им сделать наилучший выбор.

Пусть остановки пронумерованы натуральными числами от 1 до N включительно, а в городе ходит M маршрутов трамвая (все друзья ездят исключительно на трамваях и не ходят пешком между остановками). Для каждого маршрута известны номера составляющих его остановок. Пусть встретиться собираются K человек, и известно у кого сколько денег и есть ли проездной на трамвай. Цену билета считать равной 4 условным единицам.

Задача
Вам требуется найти номер такой остановки, чтобы все могли доехать до неё, и сумма денег, потраченных ими на проезд была минимальной. Естественно, можно делать пересадки с маршрута на маршрут, но учтите, что каждый раз, делая пересадку, требуется покупать новый билет: друзья зайцами не ездят. За дорогу до места встречи каждый платит сам. Денег на обратную дорогу оставлять не требуется.

Технические требования:

Входной файл: INPUT.TXT

Выходной файл: OUTPUT.TXT

Ограничение по времени тестирования: до 5 секунд на один тест

Входной файл: в первой строке даны два натуральных числа N и M, (N<=100 - количество остановок и M<=100 - количество маршрутов). В следующих M строках идёт описание маршрутов трамвая следующим образом: в начале строки находится натуральное число L<=100, задающее число остановок в маршруте. Затем идут L натуральных чисел, задающих номера остановок в маршруте. Все числа в строке разделены пробелами. Затем следует строка с натуральным числом K<=100 (K - количество человек). В следующих K строках информация для каждого из них, по строке на человека. В начале строки указано целое неотрицательное число, задающее количество денег (в условных единицах) у человека. Затем номер остановки, до которой он доходит от дома пешком, за ним следует либо число 0 (если этот человек не имеет проездного), либо 1 (если имеет). Числа в строке разделены пробелами. Никто из друзей не имеет больше 1000 условных единиц.

Выходной файл: вы должны вывести два числа: номер остановки, на которой друзья должны встретиться (если таких номеров несколько выведите наименьший) и суммарное количество денег (в условных единицах), затраченное на поездки друзьями. Числа должны быть разделены пробелом. Если друзья не смогут все встретиться на одной остановке, то вы должны вывести единственное число 0.

Пример:

INPUT.TXT
4 3
2 1 2
2 2 3
2 3 4
3
27 1 0
15 4 0
45 4 0

OUTPUT.TXT
4 12