Panda 正在玩一个游戏，在游戏中他正带领一个由 $n$ 个角色（编号为 $1$ 到 $n$）组成的队伍与恶魔的军队战斗。每个回合开始时，队伍拥有 $m$ 点可用的 Ap（能量值）。

每个角色 $i$ 拥有一个技能，可以造成 $a_i$ 点伤害，通常消耗 $c_i$ 点 Ap。在任何回合中，每个角色可以选择使用一次技能，或者什么都不做（消耗为零）。在一个回合中使用的所有技能的总 Ap 消耗不能超过 $m$。回合结束时剩余的任何 Ap 都会被丢弃，下一回合开始时队伍的 Ap 会完全恢复到 $m$ 点。

由于该游戏独特的机制，如果一个角色在某个回合中使用了技能，那么在下一个回合中，该技能的 Ap 消耗将变为 $c_i + k$。如果该角色在连续的回合中继续使用该技能，其消耗将保持在 $c_i + k$（不会进一步增加）。如果一个角色在某个回合中没有使用技能，那么在紧接着的下一个回合中，该技能的消耗将重置为 $c_i$。

Panda 想要在总共 $R$ 个回合中最大化造成的总伤害。求可能的最大总伤害。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

对于每个测试用例，第一行包含四个整数 $n, m, k, R$ ($1 \le n \le 6, 1 \le m, k \le 10^3, 1 \le R \le 10^9$)。其中 $n$ 是队伍中的角色数量，$m$ 是每个回合开始时获得的 Ap，$k$ 是使用技能时临时增加的 Ap 消耗，$R$ 是总回合数。

接下来的 $n$ 行，每行包含两个整数 $a_i, c_i$ ($1 \le a_i \le 10^6, 1 \le c_i \le m$)，分别表示角色 $i$ 的伤害和初始 Ap 消耗。

输出格式

输出一个整数，表示可以达到的最大总伤害。

样例

输入样例 1

3
3 7 1 5
59 3
13 2
81 4
5 14 2 9
66 8
20 2
25 4
39 6
57 7
4 13 7 16
18 2
13 5
33 4
7 1

输出样例 1

490
939
741