小劉穿越到了精灵宝可梦的世界，这个世界中有许多的宝可梦，你需要捕捉一些，现在给你最弱的初始宝可梦 固拉多。

所有题目共享题目背景，但题面略有不同，请仔细阅读。

题目描述

你穿越的地方处于一条野生宝可梦频繁出没的地方，你每隔一段时间就会遇见野生宝可梦。

你有 V 个精灵球，你的宝可梦 固拉多 有 K 点体力， 你遇见的第 i 个野生宝可梦都需要你消耗对应的精灵球和你的宝可梦消耗对应的体力，然后你可以获得该只宝可梦，获得一定的积分。

现在一共会出现 N 次事件，即野生宝可梦出现。每次会出现 $num_i$ 只宝可梦，我们假设小劉有两个选择：

收服： 每只需要消耗你 $a_i$ 个精灵球，需要消耗你的宝可梦 $b_i$ 点体力，捕捉后可以获得 $w_i$ 的积分。

离开： 什么也不会发生。

当固拉多的体力小于等于 0 时，小劉就必须结束狩猎（因为他需要给固拉多疗伤），

而使得固拉多体力小于等于0的野生宝可梦也不会被小劉收服。

我们现在把所有出现的野生宝可梦排成一排，可以选择两个操作：

~将连续的两个宝可梦剔除，其余数字顺次连接。

~将连续的三个宝可梦剔除，其余数字顺次连接。

你可以使用无限多次的操作并且要求你必须拿走全部的宝可梦，

请你帮助小劉求助如何操作才能小劉最多可以获得多少积分。

输入描述

第一行一个正整数 T ( 1 <= T <= $10^2$ ) 表示数据组数。

每组测试数据描述如下：

第一行两个正整数 N , V , K ( 1 $\leqslant$ N $\leqslant$ $2\times10^5$) ( 1 $\leqslant$ V $\leqslant$ $10^3$ ) (1 $\leqslant$ K $\leqslant$ $5 \times 10^2$)

分别表示出现的事件数，精灵球个数，固拉多的体力值。

接下来 N 行，每行四个整数 $num_i$ , $a_i$ , $b_i$ , $w_i$

( 1 $\leqslant$ $num_i$ $\leqslant$ 1 )

( 0 $\leqslant$ $a_i$ $\leqslant$ 0 )

( 0 $\leqslant$ $b_i$ $\leqslant$ 0 )

( $-10^9$ $\leqslant$ $w_i$ $\leqslant$ $10^9$ )

输出描述

输出最多可以获得多少积分。

样例

2
12 1000 500
1 0 0 1
1 0 0 3
1 0 0 -2
1 0 0 -1
1 0 0 -4
1 0 0 -1
1 0 0 -2
1 0 0 5
1 0 0 -4
1 0 0 15
1 0 0 -10
1 0 0 9
5 1000 500
1 0 0 1
1 0 0 2
1 0 0 3
1 0 0 4
1 0 0 5

20
15