Până în acest moment compania a produs $N$ batoane care, aflându-se pe banda de producţie, sunt dispuse în linie. Pentru fiecare baton se ştie numărul de calorii pe care o persoană le câştigă dacă mănâncă acel baton (din pacate, compania nu este specializată în producerea de batoane energizante şi de accea pot exista şi batoane pentru care numărul de calorii câştigate este negativ).

Dorel doreşte să se înfrupte cu o parte din batoane, dar pentru a nu stârni suspiciuni, a hotărât că va alege trei subsecvenţe disjuncte din secventa de $N$ batoane pe care le va mânca. Notăm aceste subsecvenţe cu $[i{~1~}, j{~1~}]$, $[i{~2~}, j{~2~}]$, $[i{~3~}, j{~3~}]$, $(1 ≤ i{~1~} ≤ j{~1~} < i{~2~} ≤ j{~2~} < i{~3~} ≤ j{~3~} ≤ N)$.

Dorel doreşte să se înfrupte cu o parte din batoane, dar pentru a nu stârni suspiciuni, a hotărât că va alege trei subsecvenţe disjuncte din secventa de $N$ batoane pe care le va mânca. Notăm aceste subsecvenţe cu $[i1, j1]$, $[i2, j2]$, $[i3, j3]$, $(1 ≤ i1 ≤ j1 < i2 ≤ j2 < i3 ≤ j3 ≤ N)$.

Desigur, menirea batoanelor energizante este de a avea cât mai multe calorii, aşadar Dorel doreşte ca suma caloriilor produse de batoanele din cele trei subsecvenţe să fie cât mai mare. Totusi, Dorel are nişte constrângeri privind subsecvenţa din mijloc. Aceasta trebuie să fie inclusă într-un anumit interval $[x, y]$ (aşadar, $x ≤ i{~2~} ≤ j{~2~} ≤ y$).

Desigur, menirea batoanelor energizante este de a avea cât mai multe calorii, aşadar Dorel doreşte ca suma caloriilor produse de batoanele din cele trei subsecvenţe să fie cât mai mare. Totusi, Dorel are nişte constrângeri privind subsecvenţa din mijloc. Aceasta trebuie să fie inclusă într-un anumit interval $[x, y]$ (aşadar, $x ≤ i2 ≤ j2 ≤ y$).

h2. Cerinta

Fiind date $M$ intervale de forma $[x, y]$ trebuie să afişaţi numărul maxim de calorii pe care le poate obţine Dorel, dacă alege trei subsecvenţe conform regulilor de mai sus.

Fiind date M intervale de forma $[x, y]$ trebuie să afişaţi numărul maxim de calorii pe care le poate obţine Dorel, dacă alege trei subsecvenţe conform regulilor de mai sus.

h2. Date de intrare