Bessie's Movie Marathon

Bessie is at the movies. Being mischievous as always, she plans to hide from Farmer John for \(L\) minutes and wants to watch movies continuously during that period.

She has \(N\) movies to choose from. For each movie, you are given its duration \(D\) and a set of showtimes. A showtime starting at time \(s\) offers an interval of availability \([s, s+D]\). Bessie may enter a movie at any moment during a showtime and leave at any time, but she is not allowed to watch the same movie twice. Also, she cannot switch from one showtime to another of the same movie if they overlap.

The task is to determine if it is possible for Bessie to watch movies continuously from time \(0\) to time \(L\). If possible, compute the minimum number of movies she must watch. If it is impossible, output \(-1\).

Input Format: The first line contains two integers \(L\) and \(N\). Then \(N\) lines follow. Each line describes a movie with the following format: first an integer \(D\) (the duration of the movie), then an integer \(K\) (the number of showtimes), followed by \(K\) integers, each representing a showtime start \(s\).

Output Format: Output a single integer which is the minimum number of movies needed for continuous watching from time \(0\) to \(L\), or \(-1\) if it is impossible.

inputFormat

The input begins with a line containing two space‐separated integers \(L\) (\(1 \leq L \leq 10^8\)) and \(N\) (\(1 \leq N \leq 20\)). Each of the following \(N\) lines describes a movie. A movie description starts with two integers: the movie's duration \(D\) and the number of showtimes \(K\). This is followed by \(K\) integers, each representing a showtime start time \(s\).

You may assume that showtimes for a movie indicate the movie is available for the interval \([s, s+D]\). Bessie can join or leave at any moment during a showtime. However, she cannot watch any movie more than once.

outputFormat

Output a single integer: the minimum number of movies required to cover the time interval from \(0\) to \(L\) continuously. If there is no valid schedule, output \(-1\).

sample

10 3
5 2 0 6
5 1 4
3 2 5 9

3