Ariciul Gălușcă este un arici obișnuit pe timp de zi. Noaptea, însă, el este de fapt eroul misterios al orașului Hedgytown – un oraș mai special, deoarece are clădiri atât deasupra solului, cât și sub pamânt, unde gravitația este inversată.

Orașul poate fi văzut ca o dreaptă (ce reprezintă solul), cu un șir de clădiri dreptunghiulare lipite deasupra solului, și un șir de clădiri dreptunghiulare lipite dedesubtul solului. Sunt N clădiri peste pământ și M sub pământ. Cele două șiruri încep și se termină la aceleași poziții. Fiecare clădire este caracterizată de trei valori: L, H și E. L reprezintă lățimea clădirii, H reprezintă înălțimea clădirii și E reprezintă efortul necesar pentru a folosi liftul din acea clădire.

Inițial, Gălușcă se afla pe partea din stânga a orașului, la nivelul solului (în dreptul primei clădiri) și trebuie să ajungă pe partea din dreapta a orașului, tot la nivelul solului (în dreptul ultimei clădiri). În acest scop, el se poate deplasa pe contururile clădirilor, consumând o unitate de efort pentru a se deplasa o unitate pe conturul unei clădiri – sau folosind lifturile.

O deplasare cu liftul este mereu de pe conturul unei clădiri până pe conturul clădirii aflate pe cealaltă parte a solului – cu alte cuvinte, când folosește liftul, ariciul nu are voie să se deplaseze doar până la sol sau să se oprească în interiorul clădirii. În cazul în care clădirea pe care se află ariciul necesită efortul E pentru a folosi liftul și clădirea de pe partea opusă a solului necesită efortul E', atunci efortul total necesar pentru a folosi liftul este E + E'.

Deplasarea cu liftul se efectuează vertical. Astfel, liftul îl va lăsa pe Gălușcă la aceeași distanță orizontală față de începutul orașului, doar că pe acoperișul clădirii opuse. Liftul nu poate fi folosit unde se întâlnesc două clădiri adiacente orizontal – nici dacă se întâlnesc pe partea solului de unde începe deplasarea, nici dacă se întâlnesc pe partea solului unde se termină deplasarea.

Deplasarea cu liftul trebuie să se efectueze strict prin interiorul clădirilor unde începe și se termină deplasarea – nu are voie să treacă prin conturul clădirilor decât la începutul și sfârșitul mișcării, și la trecerea prin sol.

O deplasare cu liftul nu are voie să se facă atunci când Gălușcă se află în dreptul graniței dintre două clădiri adiacente.
Atenție, cum Gălușcă este un erou, acesta nu va merge niciodată înapoi – doar va înainta sau va folosi lifturile.

Cerința

Se cere să se afle numărul minim de unități de efort pe care trebuie să le depună ariciul Gălușcă pentru a ajunge la destinația sa.

Date de intrare

Pe prima linie a fișierului de intrare superhedgy.in se dă N, reprezentând numărul de clădiri de deasupra solului. Pe următoarele N linii ale fișierului de intrare se dau L, H, și E, reprezentând datele clădirilor de deasupra solului, în ordinea în care sunt plasate în oraș începând cu cea mai apropiată clădire de Gălușcă. Pe linia N+2 a fișierului de intrare se află M, reprezentând numărul de clădiri dedesubtul solului. Pe următoarele M linii ale fișierului de intrare se dau L, H, și E, reprezentând datele clădirilor de dedesubtul solului, în ordinea în care sunt plasate în oraș începând cu cea mai apropiată clădire de Gălușcă.

Date de ieșire

Fișierul de ieșire superhedgy.out va conține un singur număr natural, reprezentând numarul minim de unități de efort pe care trebuie să le depună Gălușcă pentru a ajunge la destinație.

Restricții și precizări

• 1 ≤ N, M ≤ 100.000
• 1 ≤ L, H ≤ 1.000.000.000
• 0 ≤ E ≤ 1.000.000.000
• Suma lungimilor clădirilor de deasupra și de dedesubtul pământului coincid. Fie LTotal această lungime totală.
• Pentru 20 de puncte, 1 ≤ LTotal ≤ 10
• Pentru 20 de puncte, E = 0 pentru toate clădirile din oraș, 1 ≤ LTotal ≤ 100.000
• Pentru 40 de puncte, 1 ≤ LTotal ≤ 100.000
• Pentru 20 de puncte, fără restricții suplimentare

Exemplu:

superhedgy.in

3
1 2 5
3 1 1
2 3 1
4
1 4 10
2 3 1
1 2 1
2 1 1

superhedgy.out

13

Explicație

Orașul va arăta ca în figura de mai jos:

Un traseu posibil al ariciului va fi următorul:

Atenție! Deplasarea cu liftul nu s-ar fi putut efectua mai la stânga sau mai la dreapta cu 0.5 unități.