Watering the Bean Plants

Kyeonggeun gave his bean plants plenty of fertilizer and no water, so the plants rotted. This time he wants equipment that waters all of them.

The bean plants grow along $N$ line segments in the plane and fill each segment completely. Each segment joins two different points.

Kyeonggeun picks at most one point of the plane and installs a sprinkler there. The sprinkler waters every plant whose distance from that point is at most $R$, and it costs $C_1$. He may also install no sprinkler.

Every plant left outside the sprinkler range needs a waterer. One waterer is a straight piece of length exactly $1$ and waters only the plants it lies on. It cannot be cut, and one piece costs $C_2$. He places as many pieces as he wants, anywhere and in any direction, and the pieces may overlap or stick out past the end of a segment.

Compute the smallest cost of watering every plant.

The first line has the number of test cases $T$.

The first line of each test case has the number of segments $N$ ($1 \le N \le 50$), the radius $R$ of the sprinkler range ($0 \le R \le 15$), the price $C_1$ of the sprinkler ($1 \le C_1 \le 1000$), and the price $C_2$ of one waterer ($1 \le C_2 \le 1000$).

Each of the next $N$ lines has the start point $x_s$, $y_s$ and the end point $x_e$, $y_e$ of one segment, separated by spaces ($0 \le x_s, y_s, x_e, y_e \le 50$). The start point and the end point are different.

No two segments touch or overlap, and the lengths of the segments add up to at most $100$.

Every input value is an integer.

For each test case, print on its own line the smallest cost of watering every plant.