E. Роланд ба сарнай

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Роланд цэцэг тарих дуртай. Тэр саяхан координатын хавтгайн $(0, 0)$ цэг дээр гайхалтай сайхан сарнай тарьж ургуулжээ. Энэ сарнай нь үнэхээр үзэсгэлэнтэй тул Роланд муу санаатнууд сүйтгэхийг оролдох юмуу хулгайлах вий гэдгээс айж байна.

Сарнайг хамгаалахын тулд $n$ ширхэг харуулын цамхаг барихыг хүсчээ. Цамхгууд координатын хавтгайд сарнайгаас дээд тал нь $r$ зайтай байх ёстой. Роланд цамхгуудыг бүхэл тоон цэгүүд дээр байхаас гадна мѳн бүх хос цамхгуудын хоорондох зайн квадратуудын нийлбэр аль болох их байхаар барих ёстой. Анхааруулахад, Роланд нэг цэг дээр хэд хэдэн цамхаг байрлуулж болно, бүр $(0, 0)$ цэг дээр ч байрлуулж болно.

Роландад зайн квадратуудын нийлбэр хамгийн их байхаар цамхгуудаа байрлуулахад нь туслана уу. Энд хоёр цэгийн хоорондох зайг Эвклидийн хэмжээсээр авна.

Оролт

Эхний мѳр $n$, $r$ $(2 ≤ n ≤ 8; 1 ≤ r ≤ 30)$ бүхэл тоог агуулна.

Гаралт

Зайн квадратуудын нийлбэрийн хамгийн их утгыг хэвлэ. Дараагийн $n$ мѳрний $i$-р мѳрѳнд $i$-р цамхгийн байрлалыг заах $x_{i}, y_{i}$ бүхэл тоон хосыг хэвлэ. Цамхаг бүр координатын эх дээр тѳвтэй $r$ радиустай тойрог дээр юмуу дотор нь байрлах ёстой. Нэг цэг дээр хэд хэдэн цамхаг байрлуулж болно, бүр $(0, 0)$ цэг дээр ч байрлуулж болохыг анхаарна уу.

Хэд хэдэн боломжит хариу байвал дуртайгаа сонго.

Орчуулсан: Sugardorj

Жишээ тэстүүд

Оролт
4 1
Гаралт
16
0 1
0 1
0 -1
0 -1
Оролт
3 6
Гаралт
312
0 6
5 -3
-5 -3
Сэтгэгдлүүдийг ачааллаж байна...