E. Сам

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

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

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

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

Маш олон хүнд хэцүү зүйлсийг туулсны эцэст Лара Крофт эрдэнэстэй өрөөг олжээ. Түүнийг гайхшруулсан зүйл нь тус өрөөнд ямар нэгэн алтаар босгосон овоо байхгүй байв. Лара эргэн тойрноо ажиглан харангаа шалан дээр $n × m$ хэмжээ бүхий хавтангуудаас тогтох хүснэгт байгааг олж харжээ. Мөн түүнчлэн уг хүснэгтийн хавтан бүр дээр бүхэл тоо бичигдсэн байв. Хананы дэргэд маш их хэмжээний чулуунууд байрлаж байжээ. Уг өрөөний баганын дэргэдэх ширээн дээрээс Лара нэгэн тайлбар бичээс олсон ба уг бичээс дээр эрдэнэсийг олж авахын тулд хүснэгтийн мөр болгоны эхэнд байрлах 0-ээс ялгаатай тооны хавтангуудыг сонгон авч тэдгээр хавтангуудыг доош ортол дээр нь чулуунууд байрлуулах ёстой тухай бичсэн байв. Үүний дараа тэрээр сонгосон хавтангууд дээр бичигдсэн тоонуудын нийлбэртэй тэнцүү хэмжээний алтан зоостой болох ажээ. Лара маш хурдан хэрхэн чулуунуудыг байрлуулах талаар бодож эхэлсэн ба чулуунуудыг яг тавьж эхлэх гэж байхдаа тус бичээсний доор жижгээр бичсэн нэмэлт тэмдэглэл байхыг олж анзаарчээ. Уг нэмэлт тэмдэглэлд дурдсанаар сонгосон хавтангууд нь сам үүсгэж байх эрэл хайгуулчийн дээрээс тус өрөөний тааз нуран унахгүй хэмээн бичсэн байв. Мөн уг нэмэлт тэмдэглэлд хүснэгтийн мөр болгоноос сонгогдсон хавтангуудын тоог илэрхийлэх $c_{1}, c_{2}, ..., c_{n}$ дараалал нь ($c_{1}$ нь 1-р мөрнөөс сонгосон хавтангийн тоог, $c_{2}$ нь 1-р мөрнөөс сонгосон хавтангийн тоог гэх мэтчилэн илэрхийлж байна) дараах шинж чанартай байвал сонгогдсон хавтангууд нь сам үүсгэж байна хэмээн үзнэ гэж бичжээ. Үүнд: $c_{1} > c_{2} < c_{3} > c_{4} < ...$ байх буюу өөрөөр хэлбэл хөрш элементүүдийн хоорондох тэнцэтгэл бишийн тэмдэг нь байнга өөрчлөгдөж байх юм. Одоо Лара учраа олохоо байсан бөгөөд юу хийхээ сайн мэдэхгүй байв. Та түүнд туслан уг өрөөнөөс амьд гарах бөгөөд түүний авч чадах зоосны хамгийн их тоог олж өгч тусална уу.

Оролт

Эхний мөрөнд хос бүхэл тоо $n, m$ ($2 ≤ n, m ≤ 1500$) өгөгдөнө. Дараагийн $n$ мөрийн мөр болгонд $m$ ширхэг бүхэл тоо өгөгдөх ба эдгээр нь хүснэгтийг дүрслэх юм. Хүснэгт дотор байх тоонуудын абсолют утга нь $10000$-аас хэтрэхгүй байна.

Гаралт

Лара-ын авч гарч чадах зоосны хамгийн их тоог хэвлэнэ үү.

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

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

Оролт
2 2
-1 2
1 3
Гаралт
2
Сэтгэгдлүүдийг ачааллаж байна...