P11085 [ROI 2019] Student Seating (Day 2)

Translated from [ROI 2019 D2T2](https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-roi-2019-day2.pdf). 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.

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.

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 one number $P$, the minimum possible sum of discomfort after buying desks and arranging seats in an optimal way.

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$. | Subtask | Score | Special property $m$ | Special property $n$ | Special property $k$ | Other special properties | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $\le100$ | $=1$ | $\le50$ | | | $2$ | $10$ | $=1$ | $\le1000$ | $\le50$ | | | $3$ | $10$ | $\le50$ | $\le5$ | $\le3$ | | | $4$ | $10$ | $\le100$ | $\le1000$ | $=2$ | | | $5$ | $10$ | $\le100$ | $\le1000$ | $\le3$ | | | $6$ | $10$ | $\le100$ | $\le1000$ | $\le50$ | $L_i=R_i$ | | $7$ | $10$ | $\le100$ | $\le1000$ | $\le50$ | | | $8$ | $8$ | | | | $L_i=R_i$ | | $9$ | $8$ | $\le100$ | | | | | $10$ | $10$ | |$\le100$ | | | | $11$ | $4$ | | | | | 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