| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 169 | 25 | 23 | 14.744% |
Для нового кабинета школы Иннополиса требуется купить $n$ двухместных парт.
Парты бывают $k$ типов, которые задают их размер. Парта типа $i$ подходит школьникам, рост которых находится в диапазоне от $L_i$ до $R_i$ включительно. Остальным школьникам сидеть за такой партой неудобно, при этом величиной неудобства школьника, если он сидит за такой партой, будем называть модуль разности его роста и ближайшей границы диапазона этой парты. Если парта школьнику подходит, то для него величина неудобства равна нулю.
Например, если $L_i = 100$ и $R_i = 120,ドル то неудобство для школьника с ростом 80ドル$ равно 20ドル,ドル для школьника с ростом 130ドル$ равно 10ドル,ドル а для школьника с ростом 105ドル$ равно 0ドル$.
В кабинете по очереди будут заниматься $m$ групп школьников, каждая из которых состоит из 2ドルn$ человек. Известен рост каждого школьника в каждой из групп. Закупленные парты будут расставлены в классе, и в каждой группе за каждой партой будут сидеть ровно два школьника. Необходимо купить $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$ строк находится описание группы. Каждое описание состоит из 2ドルn$ целых чисел $h_1, h_2, \ldots, h_{2n},ドル задающих значение роста каждого из 2ドルn$ школьников группы (1ドル \leq h_i \leq 10^9$).
В единственной строке выходных данных выведите $P$ --- минимальную величину суммарного неудобства, которую можно достичь при оптимальной покупке парт.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $m \le 100,ドル $n = 1,ドル $k \le 50$ |
| 2 | 10 | $m = 1,ドル $n \le 1000,ドル $k \le 50$ |
| 3 | 10 | $m \le 50,ドル $n \le 5,ドル $k \le 3$ |
| 4 | 10 | $m \le 100,ドル $n \le 1000,ドル $k = 2$ |
| 5 | 10 | $m \le 100,ドル $n \le 1000,ドル $k \le 3$ |
| 6 | 10 | $m \le 100,ドル $n \le 1000,ドル $k \le 50,ドル $L_i = R_i$ |
| 7 | 10 | $m \le 100,ドル $n \le 1000,ドル $k \le 50$ |
| 8 | 8 | $L_i = R_i$ |
| 9 | 8 | $m \le 100$ |
| 10 | 10 | $n \le 100$ |
| 11 | 4 |
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
В первом примере есть только одна группа школьников, занимающаяся в классе. Следует купить по одной парте каждого вида и рассадить школьников с ростами 5ドル$ и 10ドル$ за парту первого типа, а школьников с ростами 40ドル$ и 60ドル$ за парту второго типа. В таком случае неудобно сидеть будет только школьнику с ростом 40ドル$ и соответствующая величина неудобства будет равна 10ドル$.