Поштова корпорація Багляндії, де проживає Вадим, випустила нову серію марок. Переглянувши їх, він вирішив купити декілька. Проте пошта ввела особливі правила купівлі марок. Марки розміщені в декілька однакових рядів у вигляді прямокутника, як показано на рисунку.
У комплект входить по одній марці з кожного ряду. Ви повинні купити будь-яку марку з першого ряду, а наступною обрати суміжну з другого ряду і так далі. Кожного разу ви повинні обирати марку з наступного ряду лише суміжну до тієї, що була обрана в попередньму ряді. Один з варіантів комплекту виділено на рисунку.
Вадимчик не хоче витрачати всі свої кошти, а тому просить вас допомогти йому. Вам необхідно знайти мінімальну суму, якої Вадиму вистачить для купівлі будь-якого комплекту за визначеними правилами.
P.S. Усі імена та герої вигадані, а будь-які співпадіння є випадковими.
Програма читає зі стандартного пристрою введення.
У першому рядку 2 цілих число \(N, K\) ( \( 0 < N < 10^2, 0 < K < 10^5 \) )- кількість рядів марок та загалька кількість марок у серії.
У наступних \(N\) рядках набір цілих числел \(M_{ij}\) ( \( 0 < M_{ij} < 10^6 \) ) - вартість марок відповідного ряду.
Гарантується, що усі марки можна розмістити в \(N\) рядів порівну.
Програма пише у стандартний поток виведення одне число - мінімальну суму.
4 20 2 5 3 2 6 1 4 2 6 7 1 1 1 5 7 9 9 4 1 1
9