Background

Translated from ROI 2019 D2T2.

The school wants to buy $n$ two-person desks for a new special classroom. These desks have $k$ types, and each type has different dimensions. A desk of type $i$ is suitable for students whose height is within the range from $L_i$ to $R_i$ (inclusive). For other students, sitting at this type of desk is uncomfortable. The discomfort is defined as the absolute difference between the student’s height and the nearest boundary of the suitable height range (that is, $L_i$ or $R_i$). If the desk is suitable for the student, the discomfort is $0$.

For example, if $L_i = 100,R_i = 120$, then a student with height $80$ has discomfort $20$, a student with height $130$ has discomfort $10$, and a student with height $114$ has discomfort $0$.

Students from $m$ classes will take turns coming to the special classroom for lessons, and each class has exactly $2n$ students. The purchased desks will be placed in the classroom, and each desk seats two students.

Problem Description

You are given the heights of every student in every class. You need to buy $n$ desks and arrange seats for the students of each class so that the total discomfort of all students studying in the classroom is minimized.

Write a program that, based on the information of each desk type and the students’ heights in each class, determines the minimum possible sum of discomfort that can be achieved by purchasing desks and arranging seats in an optimal way.

Input Format

The first line contains three integers $m,n,k$, representing the number of classes that will study in the classroom, the number of desks to buy, and the number of different desk types.

Each of the next $k$ lines contains two integers $L_i$ and $R_i$, describing the suitable height range for desk type $i$.

Each of the next $m$ lines contains $2n$ integers $h_1,h_2,\dots,h_{2n}$, the heights of the students in that class.

Output Format

Output one number $P$, the minimum possible sum of discomfort after buying desks and arranging seats in an optimal way.

1 2 2
5 25
50 90
60 5 10 40

10

2 3 3
200 400
300 500
100 600
300 330 440 40 30 300
150 250 350 450 550 300

130

1 3 4
10 100
200 200
10 100
300 1000
5 10 20 15 200 90

105

Hint

Explanation of Sample $1$: In the first sample, only one class studies in the classroom. You should buy one desk of each type, then seat the students with heights $5$ and $10$ at the first type of desk, and the students with heights $40$ and $60$ at the second type of desk. Then only the student with height $40$ will feel uncomfortable, with discomfort $10$.

For $100\%$ of the testdata, $1 \le m\times n \le 200000,2 \le k \le 200000,1 \le L_i \le R_i \le 10^9,1 \le h_i \le 10^9$。

Translated by ChatGPT 5