Поштова корпорація Багляндії, де проживає Вадим, випустила нову серію марок. Переглянувши їх, він вирішив купити декілька. Проте пошта ввела особливі правила купівлі марок. Марки розміщені в декілька однакових рядів у вигляді прямокутника, як показано на рисунку.

У комплект входить по одній марці з кожного ряду. Ви повинні купити будь-яку марку з першого ряду, а наступною обрати суміжну з другого ряду і так далі. Кожного разу ви повинні обирати марку з наступного ряду лише суміжну до тієї, що була обрана в попередньму ряді. Один з варіантів комплекту виділено на рисунку.

Вадимчик не хоче витрачати всі свої кошти, а тому просить вас допомогти йому. Вам необхідно знайти мінімальну суму, якої Вадиму вистачить для купівлі будь-якого комплекту за визначеними правилами.

P.S. Усі імена та герої вигадані, а будь-які співпадіння є випадковими.

Програма читає зі стандартного пристрою введення.

У першому рядку 2 цілих число \(N, K\) ( \( 0 < N < 10^2, 0 < K < 10^5 \) )- кількість рядів марок та загалька кількість марок у серії. 
У наступних \(N\) рядках набір цілих числел \(M_{ij}\) ( \( 0 < M_{ij} < 10^6 \) ) - вартість марок відповідного ряду.

Гарантується, що усі марки можна розмістити в \(N\) рядів порівну.

Програма пише у стандартний поток виведення одне число - мінімальну суму.