Zadanie

Frčiac Manhattanom

Počet bodov: 45

V pulzujúcom srdci Manhattanu, mesta, kde sa ulice krížia a semafóry blikajú sa šíri prazvláštny príbeh. Je to príbeh, ktorý sa šepká vo vetre, ktorý fúka cez betónové kaňony, príbeh, ktorý je zasadený priamo do bytia samotného mesta. Je to legenda plná mysticizmu a ponaučení, prekonávajúca generácie. Je to príbeh o tom, prečo Sliepka prešla cez cestu.

Úloha

V meste Manhattan sa nachádza \(N\) rovnomerne vzdialených horizontálnych a \(M\) rovnomerne vzdialených vertikálnych ciest. Celkovo sa teda v meste nachádza \(N \times M\) križovatiek, na ktorých sú semafory. Cez mesto sa dá prechádzať dvoma spôsobmi. Pozdĺž cesty sa dá prechádzať vždy a prejsť jednu medzeru medzi cestami trvá \(2\) minúty. Na každej križovatke je navyše semafor, ktorý určuje, či sa dá v tomto momente prechádzať cez cestu vertikálnym smerom (zo severu na juh) alebo horizontálnym smerom (zo západu na východ). Prejsť cez prechod trvá \(1\) minútu.

Smery prechodu sa na každej križovatke menia v cykloch a sú charakterizované trojicou čísel \(S_{i,j}, W_{i,j}, T_{i,j}\). V každom cykle najprv \(S_{i,j}\) minút svieti zelená v smere zo severu na juh a potom \(W_{i,j}\) minút v smere z východu na západ. Navyše vieme, že nejaký cyklus sa začal v \(T_{i,j}\)-tej minúte (pozor, smer prechodu sa menil na tomto semafore aj predtým).

Pre križovatku s parametrami \(S_{i,j} = 2, W_{i,j} = 3, T_{i,j} = 1\) by stav semafora v danej minúte vyzeral takto:

S znamená, že sa cez križovatku dá prechádzať v smere sever-juh a W znamená, že sa cez križovatku dá prechádzať v smere západ-východ.

Zistite, za aký najkratší čas sa Sliepka dokáže dostať z juhozápadného rohu mesta do severovýchodného rohu mesta.

Vstup a Výstup

Na prvom riadku vstupu sa nachádzajú \(2\) čísla \(N\) a \(M\) (\(1 \leq N, M \leq 400\)), počet ciest, ktoré vedú horizontálne a počet ciest, ktoré vedú vertikálne. Nasleduje \(N\) riadkov popisujúcich križovatky na \(i\)-tej horizontálnej ceste. Na každom z týchto riadkov sa nachádza \(M\) trojíc čísel \(S_{i,j}, W_{i,j}, T_{i,j}\) (\(1 \leq S_{i,j}, W_{i,j} \leq 10^8\), \(0 \leq T_{i,j} \leq 10^9\)) charakterizujúcich cyklus semafora na križovatke \(i\)-tej horizontálnej a \(j\)-tej vertikálnej cesty.

Na jeden riadok vypíšte najkratší čas, za ktorý sa dá dostať z juhozápadného konca mesta do severovýchodného konca mesta.

Príklad

Input:

1 1
3 2 10

Output:

4

V \(0\)-tej minúte sa dá cez križovatku prechádzať vo vertikálnom smere, teda v čase \(1\) vie byť Sliepka na severozápadnom rohu križovatky. Potom musí počkať \(2\) minúty, kým sa prepne smer prechodu na semafore a môže prejsť v horizontálnom smere do cieľa.

Input:

1 2
1 5 3 1 5 2

Output:

7

Najkratšia cesta cez mesto je zobrazená na obrázku nižšie.