Định giá vé máy bay (Plane Ticket Pricing)

Nguồn: Kattis

Phiên bản: Phước Hưng OJ Extended

Đề bài

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.

Subtask

• Subtask 1 — 20 điểm: dữ liệu nhỏ, phù hợp để kiểm tra cách trực tiếp hoặc DP cơ bản.
• Subtask 2 — 30 điểm: dữ liệu trung bình, yêu cầu lưu trạng thái hợp lý.
• Subtask 3 — 50 điểm: toàn bộ giới hạn của gói Phước Hưng OJ.

Ví dụ

Input

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

Output

23029
437

Giải thích

Kết quả được tính đúng theo quy tắc của đề. Đây là một trường hợp nhỏ để đối chiếu định dạng vào/ra trước khi nộp bài.