Các bạn thân mến, chắc hẳn các bạn đã từng được kể rằng những năm tháng sinh viên là quãng đời đầy mộng mơ, tươi đẹp nhưng cũng nhiều sóng gió. Có người từng nói Chưa từng yêu một người, chưa từng nợ một môn thì chưa từng là sinh viên. Hẳn câu nói đó đúng với rất nhiều người từng trải qua mái trường đại học. Không thiếu những giai thoại về những mối tình dai dẳng của những cô cậu sinh viên với các môn Triết học, Chính trị hay Thể dục. Những sợi dây tình yêu ấy thật khó cắt đứt, hai bên cứ cuốn lấy nhau suốt từ kì này sang kì khác; dù mình không chắc những người con trai, con gái trong mối tình đó có hạnh phúc hay không.

Còn với một số sinh viên Công nghệ thông tin; có một trải nghiệm khác cũng đi vào lòng người không kém: Tín hiệu và Hệ thống.

Buổi chiều hôm đó, thầy giáo dặn cả lớp về chuẩn bị, tuần tới thầy sẽ gọi các bạn lên bảng chữa bài để cộng điểm giữa kì. Nghe nói được cộng điểm, cả lớp mừng lắm. Nhưng nghĩ đến việc làm sao để có điểm, có vẻ các khuôn mặt rạng rỡ kia như vừa bị trúng một cơn gió độc.

Cả lớp quyết định thuê ~K~ gia sư, những người từng được A+ môn này, tới tham dự lớp học vào buổi tiếp theo. Nhiệm vụ của họ là giải thật nhanh các bài của thầy; sau đó sử dụng Bluetooth để gửi bài làm cho các bạn trong lớp.

Giảng đường được biểu diễn trên mặt phẳng toạ Descartes (Oxy). Lớp có ~N~ sinh viên, sinh viên thứ ~i~ ngồi ở vị trí có toạ độ ~(x_i~, ~y_i)~ và sử dụng điện thoại có sức mạnh ~s_i~. Lớp sẽ góp tiền mua ~K~ chiếc điện thoại có sức mạnh như nhau để phát cho ~K~ gia sư, và xếp họ ngồi vào những vị trí thích hợp trong lớp. Lưu ý: Toạ độ vị trí ngồi của ~N~ sinh viên cùng sức mạnh điện thoại của họ đều là số nguyên, nhưng toạ độ vị trí ngồi của ~K~ gia sư cùng sức mạnh các điện thoại lớp mua cho họ có thể là số thực.

Lớp muốn cả ~N~ bạn đều có thể nhận được lời giải trực tiếp và nhanh chóng từ gia sư. Gia sư ở vị trí ~(x~, ~y)~ với điện thoại sức mạnh ~s~ có thể gửi lời giải cho sinh viên ở vị trí ~(x'~, ~y')~ với điện thoại sức mạnh ~s'~ khi và chỉ khi: ~|x - x'| + |y - y'| \leq s \times s'~.

Lớp muốn biết sức mạnh tối thiểu của điện thoại cần mua cho ~K~ gia sư để tồn tại vị trí ngồi cố định của ~K~ gia sư sao cho cả ~N~ sinh viên đều nhận được lời giải trực tiếp từ ít nhất một gia sư.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~K~ ~(1 \leq N \leq 5 \times 10^{4}~, ~1 \leq K \leq 3)~ – số sinh viên của lớp và số gia sư lớp sẽ thuê.
• ~N~ dòng tiếp theo, dòng thứ ~i~ chứa ba số nguyên ~x_i~, ~y_i~ và ~s_i~ ~(1 \leq |x_i|, |y_i|, s_i \leq 10^{7})~ mô tả vị trí của sinh viên thứ ~i~ và sức mạnh điện thoại của họ.

Output

• Một số thực duy nhất là sức mạnh tối thiểu của điện thoại cần mua cho ~K~ gia sư.

Đáp án của bạn được chấp nhận nếu sai khác với đáp án của ban tổ chức không quá ~10^{-6}~.

Cụ thể, nếu đáp án của ban tổ chức là ~J~, đáp án của bạn là ~P~, bạn sẽ được điểm nếu:

$$\frac{|J - P|}{\max(1, J)} \leq 10^{-6}$$

Giới hạn

• Subtask ~1~ ~(15/60~ điểm): ~K = 1~
• Subtask ~2~ ~(24/60~ điểm): ~K = 2~
• Subtask ~3~ ~(21/60~ điểm): ~K = 3~

Sample Input 1

3 1
1 3 2
6 9 2
8 2 3

Sample Output 1

2.7500001

Sample Input 2

2 2
1 2 10
2 5 20

Sample Output 2

0.00000000 

Sample Input 3

 7 3
1 1 3
1 2 2
2 1 1
1 9 2
2 8 3
8 1 3
9 2 2

Sample Output 3

0.6667

Giải thích

• Trong ví dụ đầu tiên, gia sư duy nhất có thể xếp ở vị trí ~(4.812, 4.688)~. Từ đó gia sư có thể gửi bài giải cho cả ~3~ sinh viên.
• Trong ví dụ thứ hai, hai gia sư có thể ở gần hai sinh viên một cách tuỳ ý, nên sức mạnh của điện thoại cần thiết là rất nhỏ.
• Trong ví dụ thứ ba, vị trí của ~3~ gia sư là ~(1.667, 1.333); (1.4, 8.6); (8.6, 1.6)~.