「EZEC-1」出题

题目背景

你是一个毒瘤出题人。

题目描述

已知你有 $n$ 道毒瘤题,已经出好了题面,但数据还没出好。你还剩下 $m$ 的时间,每道题的毒瘤程度为 $a_{i}$,出数据的时间是 $x_{i}$,你有 $k$ 个老师,每个老师可以把一道题的毒瘤程度翻倍(每道题目最多被翻倍一次)。你的父母由于坚决反对你出公开赛,抢走了你的一道题,现在老师和父母的行动你都可以控制,但每位老师和父母的行为必须执行,请问你要怎么做,才能使出的题毒瘤程度之和最大?

输入输出格式

输入格式


第一行三个整数:$n,m,k$。 接下来 $n$ 行,每行 $2$ 个整数,分别是 $a_{i},x_{i}$。

输出格式


一个整数,最大的毒瘤程度之和。

输入输出样例

输入样例 #1

3 10 1
6 9
7 2
1 8

输出样例 #1

15

输入样例 #2

5 20 2
5 3 
9 7
2 6
7 8
1 2

输出样例 #2

38

输入样例 #3

3 6 2
5 4
3 3
3 3

输出样例 #3

12

说明

【样例解释】 样例 $1$ : 你控制你的父母拿走 $T1$ ,然后配 $T2$ 和 $T3$ 的数据,同时将 $T2$ 的毒瘤值翻倍,所以毒瘤值最大是 $15$ ------------ 【数据范围】 对于 $30\%$ 的数据,$ 0 \le x_{i} \le m $,$0 \le m \le 100 $,$2 \le n \le 10$,$ k<n$。 对于另外 $20\%$ 的数据,保证 $k=0$。 对于 $100\%$ 的数据,$0 \le a_{i} \le 1000$,$ 0 \le x_{i} \le m $,$0 \le m \le 1000 $,$0 \le n \le 100$,$ k<n$。