19911번 - Классные парты 서브태스크다국어

Для нового кабинета школы Иннополиса требуется купить $n$ двухместных парт.

Парты бывают $k$ типов, которые задают их размер. Парта типа $i$ подходит школьникам, рост которых находится в диапазоне от $L_i$ до $R_i$ включительно. Остальным школьникам сидеть за такой партой неудобно, при этом величиной неудобства школьника, если он сидит за такой партой, будем называть модуль разности его роста и ближайшей границы диапазона этой парты. Если парта школьнику подходит, то для него величина неудобства равна нулю.

Например, если $L_i = 100$ и $R_i = 120$, то неудобство для школьника с ростом $80$ равно $20$, для школьника с ростом $130$ равно $10$, а для школьника с ростом $105$ равно $0$.

В кабинете по очереди будут заниматься $m$ групп школьников, каждая из которых состоит из $2n$ человек. Известен рост каждого школьника в каждой из групп. Закупленные парты будут расставлены в классе, и в каждой группе за каждой партой будут сидеть ровно два школьника. Необходимо купить $n$ парт и рассадить за ними школьников каждой группы таким образом, чтобы суммарное неудобство для всех школьников, занимающихся в этом кабинете, было минимальным.

Требуется написать программу, которая по информации о каждом из $k$ типов парт и известным значениям роста каждого школьника в каждой группе определяет, какого минимального суммарного значения неудобства школьников можно достичь, купив парты и рассадив за них школьников в каждой группе оптимальным образом.

В первой строке входных данных находятся три целых числа $m$, $n$ и $k$ ($1 \le m, n \le 200\,000$; $1 \le m \cdot n \le 200\,000$; $2 \leq k \leq 200\,000$) --- количество групп школьников, которые будут заниматься в кабинете, количество парт, которые необходимо купить, и количество типов парт соответственно.

В каждой из следующих $k$ строк находятся по два целых числа $L_i$ и $R_i$ ($1 \leq L_i \leq R_i \leq 10^9$), характеризующие диапазон роста школьников, для которых подходят парты типа $i$.

В каждой из следующих $m$ строк находится описание группы. Каждое описание состоит из $2n$ целых чисел $h_1, h_2, \ldots, h_{2n}$, задающих значение роста каждого из $2n$ школьников группы ($1 \leq h_i \leq 10^9$).

В единственной строке выходных данных выведите $P$ --- минимальную величину суммарного неудобства, которую можно достичь при оптимальной покупке парт.

В первом примере есть только одна группа школьников, занимающаяся в классе. Следует купить по одной парте каждого вида и рассадить школьников с ростами $5$ и $10$ за парту первого типа, а школьников с ростами $40$ и $60$ за парту второго типа. В таком случае неудобно сидеть будет только школьнику с ростом $40$ и соответствующая величина неудобства будет равна $10$.