B. Генералд тусална уу

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

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

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

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

Нэгэн удаа Холын холын эзэнт улсад хааны ахлах генерал эрхэм Ланслот амьдран суудаг байжээ. Тэрээр өөрийн цэргүүдээрээ ихээхэн бахархдаг байсан бөгөөд эзэн хааныг урин өөрийн бэлтгэсэн тулааны техник болон тусгай салаануудын тактикийн сургуулилтуудыг харуулах дуртай байжээ. Гэвч цаг хугацаа урсан одсоор нэгэн өдөр эрхэм Ланслот Шидэт загалмайлсан эхтэй нэгэн том маргаан үүсгэжээ (Генерал загалмайлсан эхийн нисэх техникийн талаар онцгүй зүйл хэлсэн бөгөөд үүнд шидэт загалмайлсан эх ихэд гомдон уг маргаан үүссэн гэсэн цуурхал байдаг).

Уг маргааны үр дүнд загалмайлсан эх генералд нэгэн хачирхалтай хараал хийжээ. Энэ нь үнэхээр ярвигтай сонсогдож байгаа боловч нэг их гэм хортой биш байв: "Хэрэв 2 цэргийн хоорондох зайн квадрат нь $5$-тай тэнцүү байвал эдгээр цэргүүд нь хоорондоо зөрчилдөөн үүсгэх юм!"

Цэргийн сургуулилтууд нь $n × m$ хэмжээ бүхий нэгэн тэгш өнцөгт талбай дээр явагдах бөгөөд уг хүснэгтийг цэрэг бүрд зориулсан $1 × 1$ хэмжээ бүхий $nm$ ширхэг нүднүүдэд хуваасан байв. Түүнчлэн $(x_{1}, y_{1})$ болон $(x_{2}, y_{2})$ гэсэн нүднүүдэд зогсож буй цэргүүдийн хоорондох зайн квадрат нь яг $(x_{1} - x_{2})^{2} + (y_{1} - y_{2})^{2}$-тай тэнцүү байх юм. Шидэт загалмайлсан эхийн хараалаас болоод одоо бүх $nm$ ширхэг цэргүүд нь уг цэргийн сургуулилтад оролцож чадахгүй болжээ. Учир нь генерал өөрийн цэргүүдээ өөр хоорондоо зодолдохыг эсвэл бүр ч муу зүйл тохиолдохыг хүсэхгүй шүү дээ. Жишээлбэл хэрэв тэрээр $(2, 2)$ гэсэн нүдэнд цэрэг байрлуулбал $(1, 4)$, $(3, 4)$, $(4, 1)$ болон $(4, 3)$ гэсэн нүднүүдэд цэрэг байрлуулж чадахгүй байх юм. Учир нь эдгээр нүднүүдэд байрлах цэрэг болгон нь $(2, 2)$ гэсэн нүдэнд байрлах цэрэгтэй зөрчилдөөн үүсгэнэ.

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

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан бүхэл тоонууд $n$ болон $m$ ($1 ≤ n, m ≤ 1000$)-ууд өгөгдөх ба эдгээр нь сургуулилт хийх талбайн хэмжээг илэрхийлэх юм.

Гаралт

Боломжит хамгийн олон цэргийн тоог хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
2 4
Гаралт
4
Оролт
3 4
Гаралт
6

Тэмдэглэл

Эхний жишээнд эрхэм Ланслот $2 × 4$ хэмжээтэй талбай дээр дараах байдлаар 4 ширхэг цэрэг байрлуулж болох юм (цэргүүдийн байрлалуудыг саарал тойргуудаар тэмдэглэв):

2-дахь жишээнд тэрээр $3 × 4$ хэмжээтэй талбай дээр дараах байдлаар 6 ширхэг цэрэг байрлуулж болох юм:

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