题目描述

小明开始做化学实验了，现有 $n$ 种可自由组合的反应物，需要设计一个释放能量最多的化学反应。反应物可分成不同的 $k$ 类，而每种反应物有一个指标 $e_i$。全部 $k$ 类物质必须一起进行化学反应，释放的能量或吸收的能量（吸收能量用负数表示）等于同类别反应物的指标之和的乘积。为了使得这一化学反应过程稳定，参与反应的反应物必须正好有 $m$ 种。请帮小明计算单次反应释放的最大能量值。

输入格式

第一行包含三个整数 $n, m, k$，分别表示反应物的总数，参与反应的反应物数量和反应物的类别数。

接下来 $n$ 行，每行 $2$ 个数，依次描述第 $i$ 种反应物的类别 $t_i$ 和指标 $e_i$。

输出格式

输出一行 $1$ 个整数，表示答案。

输入数据#1

5 3 3
1 35
2 50
3 10
1 -100
2 -30

输出数据#1

30000

解释#1

选择第 $3, 4, 5$ 种反应物，反应可以释放 $10 \times (-100) \times (-30) = 30000$ 的能量。

输入数据#2

4 3 3
1 -35
2 50
3 10
1 -100

输出数据#2

-17500

解释#2

所有可能的反应都是吸收能量的反应（释放能量为负）。其中，吸收能量最少（释放能量最多）的反应是选择第 $1, 2, 3$ 种反应物。

输入数据#3

9 5 3
1 3
1 50
1 -2
2 0
2 1
2 -1
3 14
3 11
3 45

输出数据#3

3500

数据范围

对于全部数据，有 $1 \le n \le 80000$，$k \le m \le 1000$，$m \le n$，$1 \le t_i \le k \le 4$，$-100 \le e_i \le 100$，$k$ 类反应物各自至少有一种。

测试点

• 测试点 $1 \sim 3$（共 $30$ 分）：$m \le 50$，$k = 3$。
• 测试点 $4 \sim 6$（共 $30$ 分）：$e_i \ge 0$。
• 测试点 $7 \sim 10$（共 $40$ 分）：无特殊限制。