시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 232 75 62 31.795%

문제

희원이가 사용하는 ACM토렌트는 하나의 파일을 공유받을 때 여러 조각으로 나누어, 조각을 지닌 시드가 접속하는 시간에 시드로 부터 일부 조각을 전송 받아 파일을 완성시키는 방법으로 파일이 공유된다.  시드는 자신이 가지고 있는 조각을 자신이 접속했을 때 다른 사용자에게 배포하는 역할을 한다.

희원이는 N개의 조각으로 나눠진 하나의 파일을 공유 받으려고 한다.  각 시드 별로 접속시간과 가지고 있는 조각의 정보가 주어졌고 희원이 이외의 다른 사용자가 가지고 있는 조각은 고정되어 있다고 가정할 때 희원이가 받으려는 파일의 모든 조각을 전송 받을 수 있는 최소의 시간을 알아보자.

시드별로 가지고 있는 조각이 다르고 접속하는 시간도 다르다. 희원이는 1초당 하나의 조각을 받을 수 있다. 즉 여러 시드로부터 같은 시간에 조각을 동시에 받을 수 없다. 예를 들어 시드가 0초에 접속해서 3초에 나간다고 하면 희원이는 시드로 부터 최대 3개의 조각을 전송 받을 수 있다. 희원이는 0초부터 접속해 있다.

입력

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

두 번째 줄부터 각 테스트케이스마다 파일이 나뉘어져 있는 조각수 n(1 ≤ n ≤ 100), 시드를 나누어 가지고 있는 사람수 m(1 ≤ m ≤ 100)이 주어진다. 다음 줄부터 m개의 줄에 걸쳐 사용자별로 접속하기 시작한 시간 t1 (0 ≤ t1 ≤ 100), 나가는 시간 t2 (t1 ≤ t2 ≤ 100), 가지고 있는 조각의 수 a (0 ≤ a ≤ n), a개 조각의 각각의 번호 qi (1 ≤ qi ≤ n, 1 ≤ i ≤ a)가 주어진다.

출력

파일을 다운받을 수 있는 최소 시간을 출력한다. 만약 더 이상 접속하는 사용자가 없는데 파일을 모두 다운받지 못한 경우에는 -1을 출력한다.

예제 입력

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

예제 출력

3
10

힌트

출처

  • 문제를 만든 사람: Nada