题目描述

译自 ROI 2019 Day2 T2. Классные парты

Innopolis 学校的新教室需要买 $n$ 张双人书桌。有 $k$ 种类型的桌子可供选择，你可以决定一种类型选择几张。$i$ 型课桌适用于身高在 $L_i$ 到 $R_i$ 之间的学生。学生使用太高或太矮的课桌会感到不适，这可用「不适指数」表示，具体来说：

• 对于身高在这一区间内的学生，其不适指数为 $0$；
• 对于身高小于 $L_i$ 的学生，设身高为 $h$，则其不适程度为 $L_i - h$；
• 对于身高大于 $R_i$ 的学生，设身高为 $h$，则其不适程度为 $h - R_i$。

例如，若 $L_i = 100$，$R_i = 120$，那么身高 $80$ 的学生的不适程度为 $20$，身高 $130$ 的学生的不适程度为 $10$，身高 $105$ 的学生为 $0$。

有 $m$ 组学生轮流来教室学习，每组有 $2n$ 个人。每个组中学生的身高是已知的。每一组学习时，每张课桌应恰好坐两个学生。你需要购买 $n$ 张课桌，并为每组学生安排座位，使得这 $2mn$ 名学生的不适程度之和最小。求出这个最小的不适程度总和。

输入格式

m,n,k
接下来 k 行：L_i, R_i
接下来 m 行，每行 2n 个整数，表示一个班的每个学生的身高。

样例 1

输入

1 2 2
5 25
50 90
60 5 10 40

输出

10

解释：第 4 个小朋友的不适指数为 10，其他小朋友为 0。

样例 2

输入

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

输出

130

样例 3

输入

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

输出

105

数据范围与提示

$1 \leqslant m, n \leqslant 2\times 10^5$；$1 \leqslant m \cdot n \leqslant 2\times 10^5$；$2 \leqslant k \leqslant 2\times 10^5$；$1 \leqslant L_i \leqslant R_i \leqslant 10^9$；$1 \leqslant$ 学生身高 $\leqslant 10^9$。