E. Зохиомол бодит ертөнц

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

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

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

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

$3000$ онд зохиомол бодит ертөнцөд очих нь ердийн зүйл болжээ. Гэхдээ сайн мэдэхгүй газар луу очих нь аюултай явдал юм.

Санамсаргүй тохиолдлоор бяцхан Вася нэгэн тоглоомын зохиомол бодит байдалд орчихсон ба эргэж ирэхийн тулд энэ тоглоомын бүх үеийг амжилттай давах ёстой. Энэ тоглоомын ертөнц нь гурван хэмжээст бөгөөд энд $n$ ширхэг цэг байгаа.

Тоглоом нь $m$ үетэй бөгөөд $i$ дугаар үеийн эхэнд тоглогч нь координатыг эхийг дайрсан $Q_i$ хавтгай дээр байрлаж байх болно.

Үе бүрд Вася өгөгдсөн цэгүүдэд төвтэй $n$ бөмбөрцөг бүтээж идэвхжүүлэх бөгөөд үүний тулд тусгай робот ашигладаг. Бөмбөрцгүүдийн радиус хоорондоо ижил байх бөгөөд радиусын хэмжээг нь тоглогч өөрөө сонгоно. $R$ радиустай бөмбөрцөг бүтээхэд $R$ нэгж мөнгө зарцуулагддаг. (Тэг радиустай бөмбөрцгийг үнэгүй бүтээж болно).

Үүнээс гадна үе болгонд нэг удаа тоглогч дурын огторгуйн цэг сонгож, сонгосон цэгээ дайруулан $Q_i$ хавтгайтай перпендикуляраар лазер туяа цацаж болно. Энэ үйлдэл нь зардалгүй. Энэ лазерийн туяа дайран өнгөрсөн бөмбөрцөг идэвхжинэ. Хэрэв тоглогч бүх бөмбөрцгийг идэвхжүүлж чадвал тухайн үеийг давна. Бөмбөрцгийн төв нь $m$ үе болгонд адил боловч бөмбөрцөг нь хадгалагдахгүй гэдгийг анхаарна уу. Тоглогч нь шинэ үе болгон дээр тэднийг бүтээх ёстой.

Васяд тусалж үе тус бүрийг давахад хамгийн багадаа хичнээн хэмжээний мөнгө шаардагдах вэ гэдгийг олно уу.

Оролт

Эхний мөрөнд $n$, $m$ ($1 ≤ n ≤ 900, 1 ≤ m ≤ 100$) хоёр тоо буюу бөмбөрцгийн тоо ба тоглоомын үеийн тоо.

Дараагийн $n$ мөрөнд мөр бүрд $x_{i}$, $y_{i}$, $z_{i}$ ($0 ≤ x_{i}, y_{i}, z_{i} ≤ 10^{4}$) тоонууд буюу $i$-р бөмбөрцгийн төвийн координат. Тоглоомын явцад эдгээр цэгүүдийн байрлал нь өөрчлөгдөхгүй.

Дараагийн $m$ мөрөнд мөр бүрд $a_{i}$, $b_{i}$, $c_{i}$ ($0 ≤ a_{i}, b_{i}, c_{i} ≤ 100$, $a_{i}^{2} + b_{i}^{2} + c_{i}^{2} > 0$) тоонууд байна. Эдгээр нь тоглогч $i$ дугаар үеийн эхэнд байрлах хавтгай $Q_i$-н томьёоны ($a_{i}x + b_{i}y + c_{i}z = 0$) коэффициентүүд юм.

Гаралт

Мөр бүр $m$ тоог хэвлэнэ үү. $i$ дугаар мөрөнд $i$ дугаар үеийг давахад шаардагдах хамгийн бага мөнгөний хэмжээ байна. Системийн хариунаас $10^{-6}$-аас багаар зөрж болно.

Орчуулсан: gmunkhbaatarmn

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

Оролт
4 1
0 0 0
0 1 0
1 0 0
1 1 0
0 0 1
Гаралт
0.7071067812
Оролт
5 3
0 1 0
1 0 1
1 2 1
2 0 1
1 3 0
1 1 1
1 2 3
3 0 3
Гаралт
1.6329931619
1.6366341768
1.5411035007
Оролт
2 1
0 20 0
0 0 0
0 10 0
Гаралт
0.0000000000
Сэтгэгдлүүдийг ачааллаж байна...