P11085 [ROI 2019] 学生座位 (Day 2)

翻译自 [ROI 2019 D2T2](https://neerc.ifmo.ru/school/archive/2018-2019/ru-olymp-roi-2019-day2.pdf)。 学校要购买 $n$ 张双人桌用于新的功能教室。这些桌子有 $k$ 种类型，每种类型具有不同的尺寸。第 $i$ 种类型的桌子适合身高范围在 $L_i$ 到 $R_i$ 之间（包括边界）的学生坐，而对于其他学生来说，坐在这种桌子后是不舒服的，不舒服程度定义为学生身高与桌子适合的身高范围边界（即 $L_i$ 或 $R_i$）的差的绝对值。如果桌子适合学生，不舒服程度为零。 例如，如果 $L_i = 100,R_i = 120$，那么身高为 $80$ 的学生的不舒服程度为 $20$，身高为 $130$ 的学生的不舒服程度为 $10$，而身高为 $114$ 的学生的不舒服程度为 $0$。 $m$ 个班的学生将轮流进入功能教室上课，每个班级恰好有 $2n$ 名学生。购买的桌子将被摆放在教室中，每张桌子坐两名学生。

已知每个学生在每个班中的身高，需要购买 $n$ 张桌子并安排每个班的学生的座位，以使得在教室中学习的所有学生的总不舒服程度最小。 请编写一个程序，根据每个桌子类型的信息和每个班中学生的身高值，确定通过购买桌子并以最优方式安排学生座位所能实现的不舒服程度之和的最小值。

输入的第一行包含三个整数 $m,n,k$，分别表示将在教室中学习的班级数量、需要购买的桌子数量以及不同桌子类型的数量。 接下来的 $k$ 行中，每行包含两个整数 $L_i$ 和 $R_i$，表示适合第 $i$ 种桌子的学生身高范围。 接下来的 $m$ 行中，每行包含 $2n$ 个整数 $h_1,h_2,\dots,h_{2n}$，表示这个班中每个学生的身高。

输出一个数 $P$，表示通过购买桌子并以最优方式安排学生座位后，能实现的不舒服程度之和的最小值。

样例 $1$ 解释：在第一个样例中，只有一个班在教室里上课。应该购买每种类型的桌子一张，然后将身高为 $5$ 和 $10$ 的学生安排坐在第一种类型的桌子上，将身高为 $40$ 和 $60$ 的学生安排坐在第二种类型的桌子上。这样，只有身高为 $40$ 的学生会感到不舒服，不舒服程度为 $10$。 | 子任务 | 分值 | 特殊性质 $m$ | 特殊性质 $n$ | 特殊性质 $k$ | 其它特殊性质 | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $10$ | $\le100$ | $=1$ | $\le50$ | | | $2$ | $10$ | $=1$ | $\le1000$ | $\le50$ | | | $3$ | $10$ | $\le50$ | $\le5$ | $\le3$ | | | $4$ | $10$ | $\le100$ | $\le1000$ | $=2$ | | | $5$ | $10$ | $\le100$ | $\le1000$ | $\le3$ | | | $6$ | $10$ | $\le100$ | $\le1000$ | $\le50$ | $L_i=R_i$ | | $7$ | $10$ | $\le100$ | $\le1000$ | $\le50$ | | | $8$ | $8$ | | | | $L_i=R_i$ | | $9$ | $8$ | $\le100$ | | | | | $10$ | $10$ | |$\le100$ | | | | $11$ | $4$ | | | | | 对于 $100\%$ 的数据，$1 \le m\times n \le 200000,2 \le k \le 200000,1 \le L_i \le R_i \le 10^9,1 \le h_i \le 10^9$。