수강 신청 시스템

컴퓨터공학과 학생들은 어떤 과목을 들을지 자유롭게 고를 수 있다. 학기 초에 각 학생은 개설된 여러 과목 중 원하는 것을 골라 자신만의 시간표를 짠다. 소수의 필수 과목을 제외하면, 나머지 과목은 원하는 학생만 신청한다.

이 문제에서는 신청 절차를 다음과 같이 단순화한다. 시스템에는 $1$번부터 $n$번까지 번호가 매겨진 $n$개의 과목이 있고, 각 과목에는 수강 인원의 하한과 상한이 정해져 있다. 올해에는 $1$번부터 $m$번까지 번호가 매겨진 $m$명의 학생이 수강 신청을 하려고 한다. 각 학생은 자신이 신청할 의향이 있는 과목의 목록과, 최종적으로 수강할 과목 수의 하한과 상한을 정해 두었다. 한 학생이 같은 과목을 두 번 신청할 수는 없다.

다음 세 조건을 모두 만족하도록 학생들에게 과목을 배정할 수 있는지 판단하는 프로그램을 작성하라.

• 각 과목의 수강 인원이 그 과목에 정해진 하한과 상한 사이에 있다.
• 각 학생이 수강하는 과목 수가 그 학생에게 정해진 하한과 상한 사이에 있다.
• 각 학생이 수강하는 과목은 모두 그 학생의 선호 목록에 포함된다.

배정이 가능하다면, 모든 과목의 수강 인원 합(즉 전체 수강 신청 건수)이 최대가 되도록 배정했을 때 그 최댓값을 구하라.

첫 줄에 자연수 $T$ ($1 \le T \le 100$)가 주어진다. 이어서 $T$개의 데이터 묶음이 아래 형식으로 주어진다.

각 묶음의 첫 줄에는 두 자연수 $n$과 $m$ ($1 \le n, m \le 80$)이 주어진다. 이어지는 $n$개의 줄에는 과목별 수강 인원 제한이 주어진다. $i$번째 줄에는 두 정수 $L_i$와 $U_i$ ($1 \le L_i \le U_i \le m$)가 있으며, 각각 $i$번 과목의 수강 인원 하한과 상한이다. 이어지는 $m$개의 줄에는 학생별 제한이 같은 방식으로 주어진다. $i$번째 줄에는 두 정수 $l_i$와 $u_i$ ($1 \le l_i \le u_i \le n$)가 있으며, 각각 $i$번 학생이 수강할 과목 수의 하한과 상한이다. 이어지는 $m$개의 줄에는 학생들의 선호 목록이 주어진다. $i$번째 줄은 정수 $d_i$ ($u_i \le d_i \le n$)로 시작하고, 그 뒤에 $i$번 학생이 신청할 수 있는 서로 다른 과목 번호 $d_i$개가 주어진다.

각 데이터 묶음마다 한 줄씩 답을 출력한다. 문제의 조건을 모두 만족하는 배정이 존재하지 않으면 그 묶음에 대해 NIE를 출력한다. 존재한다면, 조건을 만족하는 배정 중 모든 과목의 수강 인원 합(전체 수강 신청 건수)이 최대일 때 그 최댓값을 정수 하나로 출력한다.

세 데이터 묶음 모두 과목이 $2$개, 학생이 $3$명이다.

첫 번째 묶음에서는 세 학생을 각자의 상한까지 배정할 수 있어 배정이 가능하며, 수강 인원 합의 최댓값은 $5$이다.

두 번째 묶음에서도 과목 인원 제한 안에서 모든 학생을 상한까지 배정할 수 있어 최댓값은 $5$이다.

세 번째 묶음에서는 $1$번 학생이 $1$번 과목만 신청할 수 있다. 이 때문에 $2$번 과목에 필요한 $3$명을 채울 수 없어 조건을 만족하는 배정이 존재하지 않으므로 NIE를 출력한다.