打怪升级

题目描述

地牢里有 $n$ 只怪物，第 $i$ 只血量为 $a_i$，打败它后获得的收益为 $b_i$。

你是一名勇者，初始时攻击力为 $s$。你有 $k$ 瓶魔法药水。每次你可以选择一个操作进行：

• 选择一个 $a_i$ 不超过当前攻击力的且没有打败过的怪物 $i$，打败它，将攻击力加上 $b_i$；
• 喝一瓶药水，将攻击力变为原来的两倍；
• 离开地牢，游戏结束。

你可以进行任意次操作。你想要知道离开地牢时你的最大攻击力是多少？

输入格式

第一行包含一个整数 $t$（$1\le t\le 100$），表示测试数据组数。接下来有 $t$ 组测试数据。每组测试数据格式如下：

第一行包含三个整数 $n,k,s$（$1\le n\le 100$，$0\le k\le 30$，$0\le s\le 10^9$），分别表示怪物数量、魔法药水数量、初始攻击力。

接下来 $n$ 行，每行包含两个非负整数 $a_i,b_i$（$0\le a_i\le10^{18}$，$0\le b_i\le 10^7$），表示第 $i$ 只怪物的血量为 $a_i$，打败它后攻击力增加 $b_i$。

输出格式

对于每组测试数据，输出一行一个整数，表示离开地牢时勇者能够获得的最大攻击力。

样例

样例输入

3
3 0 3
3 1
4 2
10 1
3 1 3
3 1
4 2
10 1
5 1 3
2 4
10 5
20 100
7 2
40 1

样例输出

6
13
124