MNPC 2010-н бодлогууд - Болхи схем

Болхи схем
Болхи схем өгөгджээ. Түүний бүтэц нь зангилаанууд болон тэдгээрийг холбосон холбогчуудаас тогтоно. Хоорондоо параллель N ширхэг утас мөн тэдгээрт перпендукляр M ширхэг утастай.(Зургийг хар)

Зураг

Мэдрэгч нь холбогч дээр байрлах ба холбогч бүр нь мэдрэгч тавихад тодорхой үнэтэй.
Мэдрэгч бүр нь холбогчоор гүйж байгаа электроны дугаар, хугацаа болон хөдөлгөөний чиглэлийг мэдээлнэ.

Мэдрэгчүүдийн мэдээллээр битүү маршрутаар (маршрут нь нэг явсан газраараа дахин явахгүй байна) явж байгаа ямар ч электроны явсан замыг нэг утгатай тодорхойлж чаддаг байхаар хамгийн бага үнэтэйгээр мэдрэгчүүдийг тавих програм бич.

Оролт:
Оролтын эхний мөрөнд T<=5 өгөгдөх ба тест бүр нь дараах бүтэцтэй. Оролтын эхний мөрд N, M (1<=200)гэсэн натурал тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана. N нь схемийн хэвтээ утасны тоо, M нь босоо утасны тоо. Дараагийн (M-1)*N мөрөнд хэвтээ холбогчуудын мэдрэгч тавих үнүүд өгөгдөнө. Эдгээрийг нь утаснуудыг дээрээс нь доошоо, холбогчуудыг нь зүүнээс баруун тийшээ байдлаар өгнө. Түүний дараагийн (N-1)*M мөрөнд босоо холбогчуудын мэдрэгч тавих үнүүд өгөгдөнө. Тэдгээрийн хувьд утаснуудыг зүүнээс баруун тийшээ, холбогчуудыг нь дээрээс доошоо байхаар өгнө. Гаралт:

Тестийн тоонд харгалзах тоонууд нэг нэг мөрөнд байрлана.
Эдгээр тоонууд нь битүү марштрутаар явах электроныг нэгэн утгатай илэрхийлж чадах нийт үнэ нь хамгийн бага байхаар байрлуулах мэдрэгчүүдийн үнүүдийг нийлбэр байна. Гаралтын төгсгөлд нэг шинэ мөр байна.
Жишээ:
Оролт:
2
3 3
2
4
7
5
2
5
7
7
3
1
2
2
2 2
3
3
2
1Гаралт:
7
1