Wedding Shopping

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

Given budget $M$ and $C$ garment categories, each with several priced models, choose exactly one model from every category. The total must not exceed $M$ and should be as large as possible. Print no solution if no complete purchase is possible.

Input

Line 1 contains $M,C$. Each of the next $C$ lines starts with $K$, followed by the $K$ model prices for that category.

Output

Print the maximum feasible spending, or no solution.

Subtasks

• Subtask 1 — 20 points: M <= 60; C <= 7; K <= 4.
• Subtask 2 — 30 points: M <= 100; C <= 12; K <= 10.
• Subtask 3 — 50 points: 1 <= M <= 200; 1 <= C <= 20; 1 <= K <= 20 for each category.

Examples

Input

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

Output

75

Explanation

One model from each category can be chosen for total 75, and no feasible complete choice spends more without exceeding 100.