Стоимость авиабилетов
Цены на билеты на самолет сильно колеблются от одной недели до следующей, и их непредсказуемость является основным источником разочарования для путешественников. Некоторые путешественники сожалеют о покупке билетов слишком рано, когда цены падают сразу после того, они покупают билеты, а некоторые путешественники сожалеют о покупке билетов слишком поздно, когда цены растут прежде, чем они собираются сделать покупку. В конце концов никто не доволен, за исключением авиакомпаний, конечно.
Безусловно, есть какая-то причина этому безумию. Оказывается, что авиакомпании изменяют цены на свои билеты динамически, в зависимости от количества доступных мест и информации о том, насколько близко полет. Например, если на рейс осталось очень мало мест, то билеты могут быть дорогими, однако в последние несколько недель до полета цены могут уменьшить чтобы заполнить пустые места. В конечном счете авиакомпании хотят максимизировать доход от каждого полета.
Вас наняла компания International Contrived Pricing Corporation (ICPC) чтобы устанавливать цены на билеты каждую неделю для авиакомпаний. Авиакомпании собрали и проанализировали исторические данные и имеют хорошие оценки по количеству мест, которые будут продаваться по определенной цене билета с определенным количеством недель до полета. Учитывая количество оставленных на рейс мест, а также число оставшихся до рейса недель, Вам следует установить цену билета на текущую неделю так, чтобы максимизировать общий доход, полученный от продажи билетов от текущей недели до начала полета. Можно предположить, что количество проданных билетов будет в точности равно оценочному, если только хватает оставшихся мест. В последнем случае все оставшиеся места будут проданы. Можно также предположить, что оптимальные цены на билеты будут выбраны за оставшиеся недели до начала полета.
Обратите внимание, что более высокие цены не обязательно означают продажу меньшего количества билетов. На самом деле более высокие цены могут иногда увеличить продажи, так как путешественники могут быть обеспокоены тем, что цены будут расти и дальше.
Входные данные
Первая строка содержит два целых числа n и w (0 < n ≤ 300, 0 ≤ w ≤ 52) - количество оставшихся мест и число недель перед полетом. Следующие w + 1 строк дают оценки для w недель, w - 1 недель, . . ., и так далее вплоть до 0 недель (то есть последней недели) до полета. Каждая из этих строк начинается числом k (0 < k ≤ 100) - количество цен на текущую неделю. Далее следуют k целых чисел 0 < p[1] < . . . < p[k] < 1000 задающих цены в долларах. Далее идут k дополнительных целых чисел s[1], ..., s[k] (0 ≤ s[i] ≤ n) указывающих число билетов, которое продадутся по соответствующим ценам.
Выходные данные
В первой строке выведите максимальную общую выручку, которую авиакомпании могут получить от продажи билетов с текущей недели до времени полета. Во второй строке выведите стоимость билета, которую следует установить на текущую неделю (w недель до полета), чтобы достичь этого максимума.
Если существует несколько наборов цен на билеты для достижения максимума, то следует выбрать самую маленькую цену билета на неделю w.