Nhà thiên văn học rất đam mê ngắm sao. Đặc biệt, ông vô cùng thích thú khi được ngắm đồng thời \(k\) ngôi sao qua kính thiên văn của mình. Chế tạo một kính thiên văn có bán kính \(r\) tốn \(t\cdot r\) krone. Khi vừa được chế tạo, kính thiên văn hướng đúng vào gốc tọa độ \((0,0)\). Việc chuyển kính sang hướng khác cũng tốn công sức: dịch chuyển điểm mà kính hướng tới một khoảng cách \(d\) tốn \(s\cdot d\) krone. Nhà thiên văn học có thể quan sát tất cả các ngôi sao cách điểm mà kính hướng tới không quá \(r\).

Chi phí nhỏ nhất để chế tạo và di chuyển kính thiên văn sao cho có thể quan sát đồng thời \(k\) ngôi sao là bao nhiêu?

Tất cả tọa độ và khoảng cách đều được xét trong mặt phẳng Euclid.

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên \(k\), \(n\), \(s\), \(t\): số ngôi sao nhà thiên văn học muốn quan sát, số ngôi sao trên bầu trời đêm nay, chi phí dịch chuyển và chi phí chế tạo kính thiên văn.

\(n\) dòng tiếp theo mô tả các ngôi sao. Dòng thứ \(i\) chứa hai tọa độ nguyên \(x_i\) và \(y_i\) của ngôi sao thứ \(i\).

Dữ liệu ra

In một số thực: số krone ít nhất mà nhà thiên văn học cần chi trả.

Kết quả được chấp nhận nếu sai số tương đối hoặc sai số tuyệt đối so với đáp án đúng không vượt quá \(\epsilon=10^{-6}\), ngoại trừ phân nhóm 6 được nêu bên dưới.

Ràng buộc

• \(1\le k\le n\le 700\).
• \(x_i,y_i\in\{-10^9,\ldots,10^9\}\) với mọi \(i\in\{1,\ldots,n\}\).
• \(s,t\in\{0,\ldots,10^9\}\).

Phân nhóm

Các bộ kiểm thử được chia thành các nhóm, mỗi nhóm có một số điểm. Để nhận được điểm của một nhóm, chương trình phải giải đúng tất cả các bộ kiểm thử trong nhóm đó. Điểm cuối cùng là điểm cao nhất của một lần nộp bài.

1. \(8\) điểm: \(t\le s\).
2. \(9\) điểm: \(n\le 50\) và \(s=0\).
3. \(18\) điểm: \(s=0\).
4. \(13\) điểm: \(n\le 50\).
5. \(14\) điểm: \(n\le 350\).
6. \(15\) điểm: ngưỡng sai số tương đối hoặc tuyệt đối là \(\epsilon=1/10\).
7. \(23\) điểm: không có ràng buộc bổ sung.

Ví dụ

2 3 1000 500
0 0
2 0
3 1

1000.0

2 3 500 3000
0 0
2 0
3 1

3387.277541898787

2 3 250 750
0 0
2 0
3 1

1000.0

2 3 0 500
0 0
2 0
3 1

353.55339059327395

3 4 0 10
0 0
10 0
5 10
5 5

50.0