Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Претходних година, филмови дуологије о великом шефу мафије ексклузивне дисјункције Окрам Ћивас постали су неки од најпопуларнијих и највољенијих на тржишту. Дуологија се састојојала од, као што име каже, два филма, који се зову Окрам и Ћивас. Међутим, услед луде популарности претходна два филма, покренула се производња за трећи и последњи део овог серијала - “Сднеирф”. У овом филму Окрам Ћивас је одавно напустио мафију и сад живи срећно са својом породицом. Међутим, онда стиже позив за један последњи задатак…

У последњој авантури нашег хероја, слично као у првој (мора да се гађа на носталгију у оваквим филмовима), он се затекао у мистериозној матрици, димензија \(N\times M\). У сваком пољу матрице је написан по један цео ненегативан број, конкретно у пољу у пресеку реда \(i\) и колоне \(j\) се иницијално налази вредност \(a_{i,j}\). После забуне око тога шта се дешава, Окрам Ћивас је схватио да има само један начин на који може да мења вредности у овој матрици. У сваком потезу, он може да изабере ненегативан цео број \(X\) и неки низ од \(N+M-1\) поља који почиње од горњег левог поља и завршава се на доњем десном, тако да свака два суседна поља у том низу деле страницу, и онда за свако поље на том путу промени вредност у њему на следећи начин: ако се пре овог потеза у овом пољу налазио број \(Y\), нова вредност у овом пољу ће бити \(Y\text{ xor }X\).

Како је Окрам Ћивас познат по својој мајсторији са ексклузивном дисјункцијом, он је себи задао следећи задатак: после произвољног броја потеза, која је најмања могућа сума свих вредности у матрици? Ако успе да минимизује суму, делује да ће успети да побегне из ове матрице и заувек напусти свет криминала.

Опис улаза

Прва линија стандардног улаза садржи два цела броја, број редова \(N\) и број колона \(M\), редом. Наредних \(N\) линија садрже по \(M\) целих бројева: \(j\)-ти број у \((i+1)\)-вој линији представља број \(a_{ij}\), који означава почетну вредност поља у \(i\)-том реду и \(j\)-тој колони.

Опис излаза

У јединој линији стандардног излаза потребно је исписати један цео број: најмању могућу суму бројева у матрици после неког броја потеза.

Пример 1

Улаз

1 2
1 0

Излаз

1

Објашњење примера

Почетна сума је један. Ово је минимална вредност јер је сума позитивна после произвољно много потеза.

Пример 2

Улаз

2 3
2 7 5
5 7 2

Излаз

0

Објашњење примера

У првом потезу Окрам Ћивас може узези \(X=7\) и низ поља \((1,1),\) \((1,2),\) \((2,2),\) \((2,3)\), а онда направи \(3\) потеза са \(X=5\) и прво низом поља \((1,1),\) \((2,1),\) \((2,2),\) \((2,3)\), затим низом поља \((1,1),\) \((1,2),\) \((1,3),\) \((2,3)\) и на крају низом \((1,1),\) \((1,2),\) \((2,2),\) \((2,3)\). ## Ограничења - \(1 \leq N,M \leq 1.500\) - \(0\leq A_{ij}\leq 1.000.000.000\)

Тест примери су подељени у 5 дисјунктних група:

Напомена

Оператор ексклузивне дисјункције у Pascal-u је означен са xor, док у C++ га записујемо помоћу симбола ^. Ова операција \(x\ \text{xor} \ y​\) се за ненегативне целе бројеве \(x,y​\) дефинише на следећи начин. Прво се бројеви запишу у бинарном запису. Уколико један број има мање цифара од другог, дописују му се водеће нуле све док не буду имали исти број бинарних цифара. Тако се добијају два низа бинарних цифара, означимо их са \(a_1, \ldots, a_k​\) и \(b_1, \ldots b_k​\). Затим се за сваку позицију \(i \in {1, \ldots, k }​\) рачуна \(c_i​\) помоћу следећих правила:

Низ бинарних цифара \(c_1, \ldots, c_k\) (који можда има водеће нуле) је бинарни запис резултата, односно броја \(x \ \text{xor} \ y\).

Ако желите да упознате са претходним авантурама Окрама Ћиваса, после такмичења можете да погледате прошлогодишњи трећи задатак за Б категорију на окружном: Окрам, као и прошлогодишњи други задатак за А категорију на окружном: Ћивас