Програмчлалын олимпиадын бодлогын архив

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

Зураг

Ийм схемээр гүйх электроныг хянах зориулалтаар холбогчууд дээр электроны дугаар, хугацаа болон хөдөлгөөний чиглэлийг мэдээлэх мэдрэгч суурилуулах шаардлагатай байжээ. Холбогч бүрийн хувьд мэдрэгч тавих үнэ нь өгөгдөнө.

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

Input

Оролтын эхний мөрөнд тестийн тоо T<=5 өгөгдөх ба тест бүр нь дараах бүтэцтэй.

Оролтын эхний мөрд N, M (1<N,M<=200)гэсэн натурал тоонууд нэг хоосон зайгаар тусгаарлагдан байрлана. N нь схемийн хэвтээ утасны тоо, M нь босоо утасны тоо.

Дараагийн (M-1)*N мөрөнд хэвтээ холбогчууд дээр тавих мэдрэгчүүдийн  үнэ өгөгдөнө. Энэ утгуудыг дээрээс нь доошоо, зүүнээс баруун тийш дараалалаар өгнө.

Түүний дараагийн (N-1)*M мөрөнд босоо холбогчууд дээр тавих мэдрэгчүүдийн үнэ өгөгдөнө. Энэ утгуудыг зүүнээс баруун тийш, дээрээс доош дарааллаар өгнө.

Output

Тестийн тоонд харгалзах тоонууд нэг нэг мөрөнд байрлана.

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

Example

Input:
2
3 3
2
4
7
5
2
5
7
7
3
1
2
2
2 2
3
3
2
1


Output:
7
1
 
Тайлбар:
 
Зураг дээр аль ч битүү маршрутаар явж байгаа электроны замыг нэг утгатайгаар тодорхойлж чаддаг байхаар 
мэдрэгчүүдийг байрлуулсныг харуулав.