토렌트

희원이가 쓰는 토렌트 프로그램은 파일 하나를 여러 조각으로 나눠서 주고받는다. 그 조각을 가진 시드가 접속해 있는 동안 희원이는 시드에게서 조각을 받아 파일을 완성한다. 시드는 자기가 접속해 있는 시간에 자기가 가진 조각을 다른 사용자에게 나눠 주는 역할을 한다.

희원이는 $n$개의 조각으로 나뉜 파일 하나를 받으려고 한다. 시드마다 접속 시간과 가진 조각이 주어지고, 희원이를 뺀 다른 사용자가 가진 조각은 바뀌지 않는다고 가정한다. 희원이가 파일의 모든 조각을 받는 데 걸리는 최소 시간을 구하자.

시드마다 가진 조각이 다르고 접속하는 시간도 다르다. 조각 하나를 받는 데 1초가 걸린다. 즉, 같은 시간에 여러 시드에서 조각을 동시에 받을 수는 없다. 예를 들어 어떤 시드가 0초에 접속해 3초에 나간다면 희원이는 그 시드에게서 조각을 최대 3개까지 받을 수 있다. 희원이는 0초부터 계속 접속해 있다.

조각에는 1번부터 $n$번까지 번호가 붙어 있다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 파일이 나뉜 조각의 개수 $n$ ($1 \le n \le 100$)과 조각을 나눠 가진 시드의 수 $m$ ($1 \le m \le 100$)이 주어진다. 이어지는 $m$개의 줄에는 시드마다 접속을 시작한 시간 $t_1$ ($0 \le t_1 \le 100$), 나가는 시간 $t_2$ ($t_1 \le t_2 \le 100$), 가진 조각의 개수 $a$ ($0 \le a \le n$), 그리고 조각 $a$개의 번호 $q_i$ ($1 \le q_i \le n$, $1 \le i \le a$)가 차례로 주어진다.

각 테스트 케이스마다 파일을 모두 받는 데 걸리는 최소 시간을 한 줄에 출력한다. 더 접속하는 시드가 없어서 받지 못한 조각이 남으면 -1을 출력한다.