eolymp
bolt
Try our new interface for solving problems
Problems

Plane Ticket Pricing

Plane Ticket Pricing

Time limit 1 second
Memory limit 64 MiB

Plane ticket prices fluctuate wildly from one week to the next, and their unpredictability is a major source of frustration for travelers. Some travelers regret buying tickets too early when the prices drop right after they purchase the tickets, and some travelers regret buying tickets too late when prices rise right before they are about to make the purchase. At the end, no one is happy, except the airlines, of course.

Surely there is some reason to this madness. It turns out that airlines price their tickets dynamically, based on how many seats are still available and how close the flight is. For example, if there are very few seats left on a flight then the tickets may be expensive until the last few weeks before the flight, at which point the prices may decrease to fill the empty seats. Ultimately, the airlines wish to maximize revenue from each flight.

You have been hired by the International Contrived Pricing Corporation (ICPC) to set ticket prices each week for airlines. The airlines have collected and analyzed historical data, and have good estimates on the number of seats that will be sold at a particular ticket price with a particular number of weeks before the flight. Given the number of seats left on a flight as well as the number of weeks left before the flight, your job is to set the ticket price for the current week, in order to maximize the total revenue obtained from ticket sales from the current week to the time of the flight. You may assume that the number of tickets sold is exactly the same as the estimates, unless there are not enough remaining seats. In that case, all remaining seats will be sold. You may also assume that the optimal ticket prices will be chosen for the remaining weeks before the flight.

Note that higher prices do not necessarily mean fewer tickets will be sold. In fact, higher prices can sometimesincrease sales as travelers may be worried that the prices will rise even higher later.

Input data

The first line contains two integers n and w (0 < n300, 0w52) - the number of seats left and the number of weeks left before the flight. The next w + 1 lines give the estimates for w weeks, w - 1 weeks, . . ., and down to 0 weeks (i.e. last week) before the flight. Each of these lines starts with an integer k (0 < k100), the number of different prices to consider that week. This is followed by k integers 0 < p[1] < . . . < p[k] < 1000 giving the prices in dollars. Finally, this is followed by k additional integers s[1], ..., s[k] (0s[i]n) indicating the number of tickets that will be sold for the corresponding prices.

Output data

On the first line, print the maximum total revenue the airline can obtain from ticket sales from the current week to the time of the flight. On the second line, print the ticket price to set for the current week (w weeks before the flight) to achieve this maximum.

If there are multiple sets of ticket prices achieving this maximum, choose the smallest ticket price for week w.

Examples

Input example #1
50 2
1 437 47
3 357 803 830 13 45 46
1 611 14
Output example #1
23029
437
Input example #2
100 3
4 195 223 439 852 92 63 15 1
2 811 893 76 27
1 638 3
1 940 38
Output example #2
83202
852
Source 2014 ACM North America - Rocky Mountain, Problem C