DA-F94-CA2-2

Time Limit: 2 Seconds Memory Limit: 131072 KB

غلام و قلی قرار است به باشگاه بدنسازی بروند. باشگاه آنها شبیه یک ماتریس ) a (با n ردیف و m ستون است و عدد a[ i ][ j ] مرتبط با هر خانه نشان دهنده ی میزان کالری سوزانده شده بعد از استفاده از دستگاه موجود در این خانه می باشد. غلام از دستگاه موجود در خانه واقع شده در ستون یک و ردیف یک a[ 1 ][ 1 ] شروع به کار کرده و قصد دارد کار خود را در خانه ی a[ n ][ m ] تمام کند. اگر غلام کار خود را در خانه ی a[ i ][ j ] تمام کند، فقط می تواند به یکی از خانه های a[ i+1 ][ j ] یا a[ i ][ j+1 ] برود. از طرف دیگر قلی از دستگاه موجود در خانه a[ n ][ 1 ] شروع به کار کرده و قصد دارد کار خود را در خانه ی a[ 1 ][ m ] تمام کند. اگر غلام کار خود را در خانه ی a[ i ][ j ] تمام کند، فقط می تواند به یکی از خانه های a[ i-1 ][ j ]یاa[ i ][ j+1 ] برود. آنها دوست دارند که در یکی از خانه های باشگاه همدیگر را ملاقات کنند و یک استراحتی داشته باشند. سپس هرکدام به کار خود ادامه می دهند و به سمت خانه های مقرر شده پیش میروند.( لزوما تعداد خانه های طی شده برای رسیدن به خانه ی مخصوص استراحت، برای قلی و غلام یکسان نیست) غلام و قلی از شما خواسته اند تا برنامه ی ای برای آنها بنویسید تا مجموع کالری سوزانده شده روی دستگاه ها بیشینه شود.

Input

در خط اول به ترتیب دو عدد n و m می آید ( 3< m , n < 1000 ). در n خط بعد، m عدد می آید که کالری سوزانده شده بعد از استفاده از دستگاه ها می باشد.

Output

جواب شامل یک عدد است که بیشینه ی مجموع کالری سوزانده شده توسط غلام و قلی بدون احتساب خانه ی استراحت است.

Sample Input

3 3
100 100 100
100 1 100
100 100 100

Sample Output

Submit