멋진 책상

시간 제한2초메모리 제한512 MB

요약

두 명이 앉는 책상 n개를 높이 범위가 정해진 k가지 종류에서 골라 사고, 각 그룹의 학생들을 짝지어 앉혀 전체 불편도의 합을 최소화하는 문제입니다.

난이도: 어려움10점 중 8점
유형: 그리디, 정렬, 이분 탐색
정답자: 아직 제출이 없습니다

문제

인노폴리스 학교의 새 교실에 두 명이 앉는 책상 $n$ 개가 필요합니다.

책상에는 크기를 정하는 종류가 $k$ 가지 있습니다. 종류 $i$ 의 책상은 키가 $L_i$ 이상 $R_i$ 이하인 학생에게 맞습니다. 범위에 들지 않는 학생은 그 책상에 앉기 불편합니다. 이런 학생의 불편도는 학생의 키와 책상 범위의 가까운 경계 사이 차이의 절댓값입니다. 책상이 학생에게 맞으면 불편도는 0입니다.

예를 들어 $L_i = 100$ , $R_i = 120$ 이면 키 80인 학생의 불편도는 20, 키 130인 학생의 불편도는 10, 키 105인 학생의 불편도는 0입니다.

$m$ 개의 그룹이 차례로 교실을 사용합니다. 각 그룹에는 $2n$ 명의 학생이 있고, 모든 학생의 키는 주어집니다. 책상은 교실에 배치되며, 각 그룹에서 책상마다 정확히 두 명이 앉습니다. $n$ 개의 책상을 사고 각 그룹의 학생을 배치하여, 교실을 사용하는 모든 학생의 불편도 합이 최소가 되게 하십시오.

입력

첫 줄에 세 정수 $m$ , $n$ , $k$ ( $1 \le m, n \le 200\,000$ ; $1 \le m \cdot n \le 200\,000$ ; $2 \le k \le 200\,000$ )가 주어집니다. 각각 그룹의 수, 사야 할 책상의 수, 책상 종류의 수입니다.

이어지는 $k$ 개의 줄에는 정수 $L_i$ 와 $R_i$ ( $1 \le L_i \le R_i \le 10^9$ )가 주어집니다. 종류 $i$ 의 책상에 맞는 키의 범위입니다.

이어지는 $m$ 개의 줄에는 각 그룹이 주어집니다. 한 줄에 $2n$ 개의 정수 $h_1, h_2, \ldots, h_{2n}$ ( $1 \le h_i \le 10^9$ )이 있으며, 그 그룹 학생들의 키입니다.

출력

책상을 최적으로 사고 각 그룹의 학생을 앉혔을 때 얻을 수 있는 불편도 합의 최솟값 $P$ 를 출력합니다.

힌트

첫 번째 예시에는 그룹이 하나뿐입니다. 종류별로 책상을 하나씩 삽니다. 키 5와 10인 학생은 종류 1의 책상에, 키 40과 60인 학생은 종류 2의 책상에 앉힙니다. 이때 불편한 학생은 키 40인 학생뿐이며, 그 불편도는 10입니다.

예제3

예제 1
입력
```
1 2 2
5 25
50 90
60 5 10 40
```
예상 출력
```
10
```

예제 2

입력

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

예상 출력

예제 3

입력

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

예상 출력