s10的游戏王卡牌

最近s10迷上了一款叫《游戏王》的卡牌游戏，简单的介绍一下这一款游戏的规则：
1. 卡牌分成魔法卡和怪兽卡两种

2. 魔法卡能直接摧毁对方场上的一只怪兽

3. 怪兽卡拥有攻击力A和星级S

4. 每回合玩家可以将手牌中的一只怪兽召唤到场上，召唤方式有三种：
4.1. 直接召唤一只4星级及以下的怪兽
4.2. 牺牲一只己方场上的怪兽，召唤一只5-6星级的怪兽
4.3. 牺牲两只己方场上的怪兽，召唤一只7-8星级的怪兽

5. 已经被召唤的怪兽将从手牌中扣除，被破坏/牺牲的场上怪兽将会被移出游戏

s10向卡牌大师qw发起了挑战，s10手中有$n$张怪兽卡，第$i$只怪兽的攻击力为$A_i$，星级为$S_i$，而qw手中有$m$张魔法卡。qw对s10这个新手很不屑，并表示在前$k$回合里他都不会使用魔法卡。而在$k$回合后，qw会一口气用掉所有魔法卡，破坏掉s10场上攻击力最高的$m$个怪兽。

而s10的任务就是在前$k$回合合理召唤怪兽，使得qw用掉魔法卡后，己方场上剩余的怪兽中攻击力最高的那只的攻击力尽量大

请问如果s10足够聪明，那么那只剩余下来后攻击力最高的怪兽的攻击力是多少？(如果s10所有怪兽都会被破坏/牺牲，那么输出0)

多组输入

每组数据第一行给定正整数$n, m, k$

接下来$n$行，每行两个整数$A_i$和$S_i$

数据范围:
$0 \le A_i \le 50000$
$1 \le S_i \le 8$
$1 \le n, m \le 100$
$k \le 120$

对于每个测试实例，请输出s10最后攻击力最高的怪兽的攻击力，每个实例的输出占一行。

6 2 10
500 1
500 1
1500 4
900 2
2000 5
3000 7
3 2 5
500 1
700 2
1900 5
3 2 2
500 1
700 2
700 3
3 1 2
500 1
700 2
700 3

1500
0
0
700

“字节跳动杯”杭州电子科技大学2019新生编程大赛