A. Хүснэгт дэхь хамгийн том тоо

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

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

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

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

$n × n$ хэмжээтэй $a$ хүснэгт нь дараах байдлаар тодорхойлогддог:

  • Бүх $i = 1, 2, ..., n$-н хувьд $a_{i, 1} = a_{1, i} = 1$ байхаар эхний багана болон эхний мөр нь нэгийн тоо агуулдаг.
  • Хүснэгтийн үлдсэн тоо бүр нь тухайн тооны зүүн талын тоо болон дээд талын тооныхоо нийлбэртэй тэнцүү. Өөрөөр хэлбэл үлдсэн тоонууд нь $a_{i, j} = a_{i - 1, j} + a_{i, j - 1}$ томьёогоор тодорхойлогдоно.

Хүснэгтийн бүх утгууд нь эдгээр нөхцлөөр тодорхойлогддог байна.

Танд $n$ тоо өгөгдөх бөгөөд та дээрх дүрмээр $n × n$ хэмжээтэй хүснэгтийн хамгийн их утгатай элементийг олох ёстой юм.

Оролт

Хүснэгтийн мөр болон баганын тоо болох $n$ ($1 ≤ n ≤ 10$) эерэг бүхэл тоог оруулна.

Гаралт

Нэг мөрөнд $m$ эерэг бүхэл тоо хэвлэнэ. Энэ нь хүснэгтийн хамгийн их утга юм.

Орчуулсан: Даариймаа

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

Оролт
1
Гаралт
1
Оролт
5
Гаралт
70

Тэмдэглэл

Хоёр дахь жишээнд хүснэгтийн мөрүүд дараах байдлаар харагдана:

1   1   1   1   1
1   2   3   4   5
1   3   6  10  15
1   4  10  20  35
1   5  15  35  70
Сэтгэгдлүүдийг ачааллаж байна...