시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Для нового кабинета школы Иннополиса требуется купить $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$ --- минимальную величину суммарного неудобства, которую можно достичь при оптимальной покупке парт.

예제 입력 1

1 2 2
5 25
50 90
60 5 10 40

예제 출력 1

10

예제 입력 2

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

예제 출력 2

130

예제 입력 3

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

예제 출력 3

105

힌트

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