D. Тэр машиныг таагаарай

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

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

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

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

Беларусын алдарт спорт тайлбарлагч Юра машины талаар их мэдлэгтэй ажээ. Тиймээс тэрээр "Тэр Машинийг Таагаарай" тоглоомт нэвтрүүлэгт оролцогчоор уригджээ.

Тоглоомын талбай нь урдаасаа хойшоогоо $4n$ метр урт, зүүнээс баруун тийшээгээ $4m$ метр өргөн тэгш өнцөгт зогсоол юм. Зогсоолыг $n + 1$ ширхэг хэвтээ болон $m + 1$ ширхэг босоо шулуунуудаар $n \times m$ ширхэг $4 \times 4$ харьцаатай квадратуудад хуваасан байв. Квадрат болгоны дотор машин байгаа. Хуваалтын шулуунууд хойноос урагшаа $0$-оос $n$ хүртэл, баруунаас зүүн тийш $0$-оос $m$ хүртэл дугаарлагдсан байв. Квадрат бүр $(i, j)$ координаттай ба баруун хойд булангийн квадратын координат нь $(1, 1)$ ба зүүн урд булангийнх нь $(n, m)$ координаттай байв.

Тоглоом эхлэхээс өмнө зохион байгуулагч Юраг хуваалтын шулуунуудын $(n + 1)(m + 1)$ ширхэг огтлолцолын цэгээс аль нэг дээр нь зогсохыг хүсэв. Дараа нь тоглоом дуустал машинуудыг тааж эхэлнэ. Юра машины талаар их өндөр мэдлэгтэй тул тэр бүх машиныг тааж чадна, харин гол нь цаг хугацаа юм. Тэрээр машин бүрийг таахад түүний сонгосон цэгээс тэр машин байрлаж буй квадратын төв хүртэлх зайн квадратыг тухайн машины ховор тохиолдлын үзүүлэлт болох $c$-ээр үржүүлсэнтэй тэнцүү хугацаа шаардагддаг. Өөрөөр хэлбэл Юрагийн зогссон цэгээс $d$ зайд байх төвтэй квадрат доторх машинийг таахад $c \cdot d^{2}$ секүнд зарцуулдаг байна.

Тэрээр бүх машины ховор тохиолдлын үзүүлэлтүүдийг нь мэддэг. Түүнд хамгийн бага хугацаа зарцуулдаг байх байрлалыг нь олоход туслаарай.

Оролт

Эхний мөрөнд зогсоолийн талбайн хэмжээс болох $n$ ба $m$ $(1 ≤ n, m ≤ 1000)$ бүхэл тоонууд байрлана. Дараагийн $n$ мөр бүрт $m$ бүхэл тоо байна. $i$ дэх мөрний $j$-дэх тоо нь $(i, j)$ координаттай квадрат дахь машины ховор тохиолдлын үзүүлэлт $c_{ij}$ ($0 ≤ c_{ij} ≤ 100000$) байна.

Гаралт

Эхний мөрөнд боломжит хамгийн бага хугацааг хэвлэнэ. Дараагийн мөрөнд Юрагийн зогсвол зохих огтлолцлын цэгийн шулуунуудын дугаар $l_{i}$ ба $l_{j}$ ($0 ≤ l_{i} ≤ n, 0 ≤ l_{j} ≤ m$)-г хэвлэ. Хэрэв олон хувилбар байвал аль $l_{i}$-ийн утга багатайг нь хэвлэ. Мөн л хувилбар нь олон янз байвал $l_{j}$-ийн аль бага утгатайг нь хэвлэ.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: Бат-Од

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

Оролт
2 3
3 4 5
3 9 1
Гаралт
392
1 1
Оролт
3 4
1 0 0 0
0 0 3 0
0 0 5 5
Гаралт
240
2 3

Тэмдэглэл

Эхний жишээн дээр нийт хамгийн бага хугацаа нь $3 \cdot 8 + 3 \cdot 8 + 4 \cdot 8 + 9 \cdot 8 + 5 \cdot 40 + 1 \cdot 40 = 392$ байна.

Сэтгэгдлүүдийг ачааллаж байна...