Description

预测未来$T$天的股市。

在第$i$天可以以$A$$P_i$的价格购买一只股票，或者以$B$$P_i$的价格卖出一只股票。

在第$i$天最多买$A$$S_i$只股票，最多卖$B$$S_i$只股票。

两个交易日的间隔应大于$W$天。

也就是说，假设在第$i$天交易$（$任何买卖股票都被视为交易$）$，则下一个交易日必须是第$（$$i$+$W$+$1$$）$天或更晚。

在任何时候都不可以拥有超过$m$$a$$x$$P$只股票。

第$1$天之前，小明已经有了无限多的钱，但没有股票，他想从股票市场尽可能多地赚钱。

Format

Input

第$1$行是一个整数$t$，表示测试用例的数量。

每个测试用例的第$1$行都是三个整数$T$、$m$$a$$x$$P$、$W$，$0$$≤$$W$$<$$T$$≤$$2$$0$$0$$0$，$1$$≤$$m$$a$$x$$P$$≤$$2$$0$$0$$0$。

接下来的$T$行各有$4$个整数$A$$P_i$、$B$$P_i$、$A$$S_i$、$B$$S_i$，$1$$≤$$B$$P_i$$≤$$A$$P_i$$≤$$1$$0$$0$$0$，$1$$≤$$A$$S_i$，$B$$S_i$$≤$$m$$a$$x$$P$。

Output

单行输出小明赚得最多的钱数。

Samples

1
5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1

3