U279659 [太戈 1937] 火烧藏经阁

有一座藏经阁，里面收藏着历代古籍非常珍贵。但是不幸的事情发生了，突发一场大火将藏经阁中的大量古籍书籍烧成灰烬。你作为消防队队长冲入火海，发现还有一个书架没有被大火侵袭，于是你希望能尽力守护剩余的古籍。由于你一个人势单力薄，最多只能带走m本书籍。书架共n层，编号1到n。其中第i层共c[i]本书，从左到右依次贴有价值标签，v[i][j]代表书架的第i层从左到右第j本书的价值。但是你发现一件棘手的事情：每层书籍排布非常紧密，你无法从中间抽出书籍，必须从每层左端或右端拿出书籍。时间紧迫，若你只可以从每层两端取出连续若干本书，总数量不超过m本，请问最多可以抢救多少价值的古籍？

输入文件books.in 输入第一行为正整数n,m，n

输出文件books.out 输出一个整数。

样例 #1 说明： 第一层取3+7，第二层取5.