Plane Ticket Pricing

Source: Kattis

Version: Phuoc Hung OJ Extended

Problem Statement

This package preserves the original task mechanism. Một chuyến bay còn $N$ ghế và còn $W$ tuần trước khi bay. Với mỗi tuần, hãng có một số mức giá; dữ liệu lịch sử cho biết chính xác số vé sẽ bán ở từng mức giá, nhưng không thể bán vượt quá số ghế còn lại. Hãy tối đa hóa tổng doanh thu từ tuần hiện tại đến chuyến bay.

Input

Dòng đầu chứa $N,W$. Sau đó có $W+1$ dòng, theo thứ tự từ tuần hiện tại đến tuần cuối. Mỗi dòng bắt đầu bằng $K$, tiếp theo là $K$ mức giá tăng dần rồi $K$ số lượng vé dự kiến bán tương ứng.

Output

Dòng 1 in doanh thu tối đa. Dòng 2 in mức giá nhỏ nhất nên đặt ở tuần hiện tại trong số các phương án tối ưu.

Subtasks

• Subtask 1 — 20 points: small data.
• Subtask 2 — 30 points: medium data.
• Subtask 3 — 50 points: full PHOJ package limits.

Examples

Input

50 2
1 437 47
3 357 803 830 13 45 46
1 611 14

Output

23029
437

Explanation

The output follows directly from the rules above.