Minimizing Total Discomfort in Classroom Seating Arrangement

Given the heights of students in each class and available desk types – each with a fixed height and a limited quantity – the task is to purchase exactly as many desks as there are students and assign each student a desk. The discomfort for a student is defined as the absolute difference between the student’s height and the desk’s height, i.e., \(|student height - desk height|\). Find the minimum total discomfort achievable by an optimal assignment of desks to students.

If the total number of available desks is less than the number of students, output -1.

inputFormat

The input begins with an integer c representing the number of classes. Each of the following c lines describes a class. A class description starts with an integer k_i (the number of students in the class) followed by k_i integers which are the heights of the students in that class.

After the classes, there is an integer t denoting the number of available desk types. Each of the following t lines contains two integers: the first is the available quantity of that desk type, and the second is the desk’s height.

outputFormat

Output a single integer representing the minimum total discomfort achievable if all students are assigned a desk. If it is impossible to seat all students (i.e. the total available desks is less than the number of students), output -1.

sample

2
2 150 160
3 155 165 170
2
3 155
3 165

15