superhedgy

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 pămâ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. Atenție, cum Gălușcă este un erou, acesta nu va merge niciodată înapoi — doar va înainta sau va folosi lifturile.

Cerință

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 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 oras, î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 ieșire

În fișierul de ieșire superhedgy.out se va afișa un singur număr natural, reprezentând numărul minim de unități de efort pe care trebuie să le depună Gălușcă pentru a ajunge la destinație.

Restricții

• 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 $L_{Total}$ această lungime totală.
• Pentru 20 de puncte: $1 ≤ L_{Total} ≤ 10$
• Pentru alte 20 de puncte: E = 0 pentru toate clădirile din oraș, $1 ≤ L_{Total} ≤ 100 000$
• Pentru alte 40 de puncte: $1 ≤ L_{Total} ≤ 100 000$
• Pentru alte 20 de puncte: Fără restricții suplimentare

Exemple

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.