E. Чөтгөрийн Ертөнц

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

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

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

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

Пинки болон Брэйн нарын Ларж Хадрон Коллайдэр-д хийсэн нэгэн нууцлаг туршилтын үр дүнд зэргэлдээх хэмжээст орон зай уруу хөтлөх хар нүх шиг хаалганууд нээгджээ. Ингэснээр Чөтгөрийн ертөнцийн тэмтрүүлнүүд манай ертөнц уруу мөлхөн орсон байна. Брэйн маш хурдан уг нөхцөл байдлыг дүгнэсэн бөгөөд тэрээр илүү олон чөтгөрийн тэмтрүүлүүд уг хаалганаас гарч ирэх ба эрх чөлөөтэй болно гэдгийг ойлгожээ. Гэвч үүнээс илүүтэйгээр тэрээр дэлхий ертөнцийг захирах боломжтой болохоо ойлгосон байна.

Коллайдэр-ийн барилга нь цилиндр дотор багтсан нэгэн тэгш өнцөгт хэлбэртэй бөгөөд энэ нь доорх зурагт дүрсэлсэнтэй ижлээр $n$ ширхэг мөр болон $m$ ширхэг баганаас тогтсон байх юм.

Уг жишээ зурагт $n = 4$, $m = 5$ байна. Энд дүрсэлсэн тасархай зураас нь багана бүрийг цагираглах нэгэн коридорыг илэрхийлэх ба өөрөөр хэлбэл уг коридор нь $n$-р мөр болон $1$-р мөрүүдийг холбож байх юм.

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

Брэйн эдгээр бүх тэмтрүүлүүд нь хүснэгтээс гарч чадвал ихэд баярлах боловч тэрээр нэгэн асуудалтай тулгарчээ: Хязгааргүй тооны тэмтрүүлүүд хаалгануудаас гарч ирж болох ба тэмтрүүл болгон нь хязгааргүй урт бөгөөд тодорхой хэмжээний өргөнтэй байх ажээ. Харамсалтай нь коридоруудын эзлэхүүн нь хязгаарлагдсан байх юм. Мөн Брэйн коридор болгоноор дамжин мөлхөх тэмтрүүлүүдийн хамгийн их тоог ойролцоогоор тооцоолж чадаж байв.

Одоо Брэйн хулганад туслан Ларж Хадрон Коллайдэр-аас мөлхөн гарах Чөтгөрийн ертөнцийн тэмтрүүлүүдийн хамгийн их тоог тодорхойлж өгнө үү.

Оролт

Оролтын эхний мөрөнд 2 бүхэл тоо $n$ болон $m$ ($2 ≤ n ≤ 5$, $2 ≤ m ≤ 10^{5}$) өгөгдөнө. Эдгээр нь Ларж Хадрон Коллайдэр-ын хүснэгтийн хэмжээнүүдийг илэрхийлнэ. Дараагийн $m - 1$ мөрийн мөр болгонд $n$ ширхэг тоо өгөгдөнө. Эдгээр нь хөндлөн коридоруудын багтаамжуудыг илэрхийлэх юм. Дараагийн $m$ мөрийн мөр болгонд $n$ ширхэг тоо өгөгдөнө. Эдгээр нь босоо коридоруудын багтаамжуудыг илэрхийлэх юм. Коридорууд нь зүүнээс баруун хүртэл болон дээрээс доош хүртэл гэсэн дарааллын дагуу дүрслэгдсэн байна. $n$-дэх босоо коридор болгон нь $n$-р мөр болон $1$-р мөр дээрх зангилааны цэгүүдийг холбож байх юм. Ямар нэгэн коридорын багтаамж нь сөрөг-биш бүхэл тоо байх бөгөөд $10^{9}$-аас хэтрээгүй байна.

Гаралт

Пинки болон Брэйн нарын удирдах Чөтгөрийн ертөнцийн тэмтрүүлүүдийн тоог илэрхийлэх ганц тоог хэвлэнэ үү.

C++ дээр 64-битийн бүхэл тоонуудыг унших болон бичихдээ %lld гэсэн тодорхойлогчийг бүү хэрэглэнэ үү. Харин use cout эсвэл %I64d гэсэн тодорхойлогчийг хэрэглэхийг илүүд үзнэ үү.

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

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

Оролт
3 4
4 4 4
1 1 5
5 5 3
4 1 2
1 3 1
3 5 4
1 4 3
Гаралт
7
Оролт
2 2
9 2
2 3
6 1
Гаралт
11
Сэтгэгдлүүдийг ачааллаж байна...