会议室调度优化

题目描述

Y 同学作为一名秘书，需要为一个部门安排会议。

资源与约束：

• 办公大楼共 $F$ 层，从 $1$ 到 $F$ 编号。
• 每层楼有 $M$ 间相同的会议室。
• 一天内，每间会议室最多只能安排一场会议。
• 一场会议的标准时长为 $2$ 个单位时间。

会议申请：

• 共有 $N$ 条会议申请。第 $i$ 条申请希望在楼层 $R_i$ 召开，参会人数为 $P_i$。
• 申请人只会在自己所在的楼层 $R_i$ 提出申请。

调度规则：

• 一场申请在 $R_i$ 楼的会议，可以被安排在 $R_i$ 楼或其下方的任意楼层 $k$（$1 \le k \le R_i$）。
• 如果会议被安排在非申请楼层 $k$，由于人员需要移动，会产生额外的时间消耗。每向下一层，耗时增加 $1$ 个单位时间。

成本计算：

• 一场申请在 $R_i$ 楼、参会人数为 $P_i$、最终被安排在 $k$ 楼的会议，其总人时消耗为： $ P_i \times (\text{标准时长} + \text{移动耗时}) = P_i \times (2 + (R_i - k)) $

你的任务是，为所有 $N$ 场会议制定一个合法的分配方案（即每间会议室最多一场会议），使得所有会议的总人时消耗之和最小。如果无法满足所有会议申请，则判定为无解。

输入格式

第一行包含三个整数 $F, M, N$。

接下来的 $N$ 行，每行包含两个整数 $R_i, P_i$，描述一条会议申请。

输出格式

输出一个整数，表示可以达成的最小总人时消耗。如果无法为所有会议安排房间，则输出 -1。

样例

样例输入 #1

4 1 3
3 10
1 10
3 20

样例输出 #1

90

样例输入 #2

3 3 4
2 20
1 10
2 10
2 10

样例输出 #2

100

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le F \le 1000$
• $1 \le M \le 100$
• $1 \le N \le 100000$
• $1 \le R_i \le F$
• $1 \le P_i \le 50$