Mua sắm đám cưới (Wedding Shopping)

Nguồn: UVa

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

Đề bài

Có ngân sách $M$ và $C$ nhóm trang phục. Mỗi nhóm có nhiều mẫu với giá cho trước. Phải mua đúng một mẫu từ mỗi nhóm, tổng tiền không vượt $M$, và cần chi nhiều nhất có thể. Nếu không thể mua đủ, in no solution.

Input

Dòng 1 chứa $M,C$. Mỗi trong $C$ dòng tiếp theo bắt đầu bằng $K$, sau đó là $K$ giá của các mẫu thuộc nhóm đó.

Output

In số tiền lớn nhất có thể chi mà vẫn mua đủ, hoặc no solution.

Subtask

• Subtask 1 — 20 điểm: M <= 60; C <= 7; K <= 4. Mức này dành cho cách trực tiếp hoặc đệ quy nhỏ.
• Subtask 2 — 30 điểm: M <= 100; C <= 12; K <= 10. Mức này yêu cầu nhận ra trạng thái DP và loại bỏ tính toán lặp.
• Subtask 3 — 50 điểm: 1 <= M <= 200; 1 <= C <= 20; 1 <= K <= 20 for each category. Đây là toàn bộ giới hạn của bài.

Ví dụ

Input

100 4
3 8 6 4
2 5 10
4 1 3 3 7
4 50 14 23 8

Output

75

Giải thích

Có thể chọn một mẫu ở mỗi nhóm với tổng 75 và không có tổ hợp hợp lệ nào có tổng lớn hơn mà không vượt 100.