Description

Recently wywcgs is interested in stones very much. In the past contest, wywcgs has a stone transportation problem. In that problem, he finds a kind of very beautiful stone which made in city A. wywcgs wants to buy this stone as many as possible. These stones must be transfered to the city B that wywcgs lives along a path from A to B. There will be some roads which doesn't have enough capacity to transfer all the stones, so wywcgs must spend money to widen them. But wywcgs has only a little money, so he wants to make an optimal plan to buy and transfer them.

In that problem, wywcgs transfers these stones only along a single path. But he realized that it's better to transfer them along multiple paths. That is to say, he can divide these stones into some groups and transfer each of them along a different path respectively. Now he wants to design a new plan to buy and transfer them.

Input

Input contains multiple test cases. The first line is a integer T, the number of test cases. Each case begins with three integers N, M, C, P, with 2 <= N <= 1000, 1 <= M <= 10000, 1 <= C <= 100000000, 1 <= P <= 10000, represents the number of city, the number of road, the maximum money wywcgs can spend, the cost of one stone respectively. Next M lines each denotes a road. A road is represented by four numbers u, v, c1, c2, with 0 <= u, v < N, 0 <= c1 <= 10000, 0 <= c2 <= 10000, means this road connects the city u and v, its capacity is c1 and wywcgs must spend c2 money to widen its capacity by one. Cities are numbered from 0 to N-1. City 0 is always A, and city 1 is always B. Roads are all bidirectional, and there may be two or more roads connecting to the same pair of city.

Output

For each test case, output a line contains a integer which means the maximum number of wywcgs can buy.

Sample Input

4
            2 1 1000 1
            0 1 0 2
            2 1 1000 1
            0 1 1 2
            3 1 100000000 1
            0 2 10000 0
            4 4 4 1
            0 2 1 1000
            2 1 1 1000
            0 3 1 0
            3 1 1 1
            

Sample Output

333
            334
            0
            3
            

Hint

Sample 3 : there is no path bwtween 0 and 1, so wywcgs cannot get any stones no matter how much money he has.
Sample 4 : wywcgs can buy 3 stones, 1 stone is transfered along the path 0->2->1 with cost 0, and the other 2 stones are along 0->3->1 with cost 1.