Plane Ticket Pricing

Plane ticket prices swing from one week to the next, and travellers cannot predict them. Some buy early and watch the price drop a few days later. Some wait and watch the price climb right before they pay. Only the airline comes out happy.

There is a system behind the swings. An airline prices a flight dynamically, using the number of seats still available and the number of weeks left before departure. When few seats remain, the price can stay high until the final weeks and then fall to fill the cabin. The airline wants the largest possible revenue from the flight.

The International Contrived Pricing Corporation has hired you to set the ticket price each week. The airline studied its historical data and can estimate how many seats sell at a given price with a given number of weeks left. Given the seats still available and the number of weeks left before the flight, set this week's price so that the revenue collected from this week through the week of the flight is as large as possible.

Assume that the number of tickets sold matches the estimate exactly, unless fewer seats remain. In that case every remaining seat sells. Assume also that the price of every later week is chosen optimally.

A higher price does not always sell fewer tickets. A higher price sometimes sells more, because travellers worry that the price will climb even further.

The input describes one flight. The first line contains two integers $N$ and $W$, the number of seats left and the number of weeks left before the flight ($0 < N \le 300$, $0 \le W \le 52$).

The next $W + 1$ lines hold the estimates for $W, W - 1, \dots, 0$ weeks left, in that order. The line for $0$ weeks left is the last week. Each of these lines starts with an integer $K$, the number of prices to consider that week ($0 < K \le 100$). Then come $K$ integers $p_1, \dots, p_K$, the prices in dollars ($0 < p_1 < \cdots < p_K < 1000$). Then come $K$ more integers $s_1, \dots, s_K$ ($0 \le s_i \le N$), where $s_i$ is the number of tickets that sell at price $p_i$.

On the first line, print the largest total revenue the airline can collect from ticket sales, counted from the current week through the week of the flight. On the second line, print the price to set for the current week, which is $W$ weeks before the flight.

If several sets of prices reach that maximum revenue, print the smallest price for week $W$.