题目描述

译自 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 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

数据范围与提示

$1 ⩽ m, n ⩽ 2\times 10^5$; $1 ⩽ m · n ⩽ 2\times 10^5$; $2 ⩽ k ⩽ 2\times 10^5$; $1 ⩽ L_i ⩽ R_i ⩽ 10^9$; $1 ⩽$ 学生身高 $⩽ 10^9$.