ДАРХАНЫ 26-р ДУНД СУРГУУЛЬ / RUSSIAN /

N*M хэмжээст тэгш өнцөгтийн зүүн дээд буланд тоглогч байрлаж байгаа. Нүд бүрт тоо бичигдсэн байгаа. 1 нүүдлээр баруун эсвэл доод хөрш нүдэнд очихыг зөвшөөрнө. Харин зүүн эсвэл дээд хөрш нүд рүү шилжих хориотой. Эхний болон сүүлийн нүднүүдээ оролцуулаад шилжиж ирсэн нүднүүдийнхээ тоог цуглуулна. Тоглогчийн баруун доод нүдэнд очиж болох хамгийн бага нийлбэрийг ол.

Input

Тэгш өнцөгтийг хэмжээс болох N,M тоонууд нэг мөрөнд зайгаар тусгаарлагдан өгөгдөнө.

(1<=N<=20, 1<=M<=20)

Дараагийн N мөрөнд [1;100] завсарт харьяалагдах M тоонууд зайгаар тусгаалагдан өгөгдөнө.

Output

Хамгийн бага нийлбэр.

Example

Input:
3 4
1 1 1 1
5 2 2 100
9 4 2 1  Output: 8