콩나무 물주기

경근이는 콩나무에 비료만 잔뜩 주고 물은 주지 않아 콩나무를 썩혔다. 이번에는 설비를 갖춰 모든 콩나무에 물을 주려고 한다.

콩나무는 2차원 평면에 놓인 선분 $N$개를 따라 빈틈없이 심어져 있다. 각 선분은 서로 다른 두 점을 잇는다.

경근이는 평면에서 점을 최대 한 개 골라 그 자리에 스프링클러를 설치한다. 스프링클러를 설치하면 그 점에서 거리가 $R$ 이내인 콩나무에 물이 자동으로 공급되고, 설치 비용은 $C_1$이다. 스프링클러를 설치하지 않아도 된다.

스프링클러의 범위 밖에 남은 콩나무에는 수분공급기를 놓는다. 수분공급기 하나는 길이가 정확히 $1$인 곧은 조각이고, 자기가 지나는 자리의 콩나무에만 물을 준다. 잘라서 쓸 수 없으며 값은 하나에 $C_2$이다. 평면 어디에나 원하는 방향으로 원하는 개수만큼 놓고, 서로 겹치거나 선분 밖으로 삐져나와도 된다.

모든 콩나무에 물을 주는 최소 비용을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 선분의 개수 $N$ ($1 \le N \le 50$), 스프링클러가 물을 주는 범위의 반지름 $R$ ($0 \le R \le 15$), 스프링클러의 가격 $C_1$ ($1 \le C_1 \le 1000$), 수분공급기 하나의 가격 $C_2$ ($1 \le C_2 \le 1000$)가 주어진다.

이어지는 $N$개의 줄에는 선분의 시작점 $x_s$, $y_s$와 끝점 $x_e$, $y_e$가 공백으로 구분되어 주어진다 ($0 \le x_s, y_s, x_e, y_e \le 50$). 시작점과 끝점은 서로 다르다.

선분끼리는 닿거나 겹치지 않고, 선분 길이의 총합은 $100$ 이하이다.

입력은 모두 정수이다.

각 테스트 케이스마다 모든 콩나무에 물을 주는 최소 비용을 한 줄에 출력한다.