当前没有测试数据。

题目描述

小明开始做化学实验了，现有 $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

30000

解释#1

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

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

-17500

解释#2

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

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

3500

数据范围

• 对于全部数据，有 $1\le n\le 80000$，$k\le m\le 1000$，$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$ 分）：无特殊限制。