Lumini

La festivalul "MusicFest", scena principală este dotată cu o instalație de $N$ lumini de ultimă generație, aranjate liniar și numerotate de la $1$ la $N$. Inițial, toate cele $N$ lumini au intensitatea $0$. Directorul tehnic a pregătit $M$ efecte speciale. Fiecare efect $i$ (pentru $1 \leq i \leq M$) este descris prin trei valori: $st_i$, $dr_i$ și $val_i$. Când acest efect este activat, intensitatea fiecărei lumini din intervalul $[st_i, dr_i]$ (inclusiv) crește cu valoarea $val_i$. Acesta dorește să analizeze eficiența show-ului de lumini și are nevoie de ajutorul tău pentru a calcula două statistici.

Cerință

Scrieți un program care, cunoscând $N$, $M$ și cele $M$ efecte, determină:

1. Suma totală a intensităților tuturor celor $N$ lumini, după aplicarea tuturor celor $M$ efecte.
2. Intensitatea maximă atinsă de oricare lumină de pe scenă, după aplicarea celor $M$ efecte.

Date de intrare

Fișierul de intrare lumini.in conține pe prima linie un număr $c$, reprezentând cerința ($1$ sau $2$). Pe a doua linie se află două numere naturale $N$ și $M$, separate printr-un spațiu, reprezentând numărul de lumini și, respectiv, numărul de efecte. Pe următoarele $M$ linii se află câte trei numere naturale $st_i$, $dr_i$ și $val_i$, separate prin spații, reprezentând descrierea fiecărui efect $i$.

Date de ieșire

Fișierul de ieșire lumini.out va conține o singură linie pe care va fi scris:

• dacă $c = 1$: un singur număr reprezentând suma totală a intensităților.
• dacă $c = 2$: un singur număr reprezentând intensitatea maximă atinsă.

Restricții și precizări

• $1 \leq N, M \leq 200 \ 000$
• $1 \leq st_i \leq dr_i \leq N$
• $1 \leq val_i \leq 1 \ 000$
• Se garantează că intensitatea maximă (pentru cerința 2) nu va depăși $2^{31}-1$.
• Se garantează că suma totală (pentru cerința $1$) nu va depăși $2^{63}-1$.
• Problema este împărțită în două cerințe. Testele corespunzătoare fiecărei cerințe valorează 45 de puncte.

Exemplul 1

lumini.in

1
8 4
1 4 10
3 6 5
2 5 20
7 8 8

lumini.out

156

Explicație

Cerința 1 (Suma):

Avem $N = 8$ lumini și $4$ actualizări:

1. $1 \ 4 \ 10 \rightarrow 10 \ 10 \ 10 \ 10 \ 0 \ 0 \ 0 \ 0$
2. $3 \ 6 \ 5 \rightarrow 10 \ 10 \ 15 \ 15 \ 5 \ 5 \ 0 \ 0$
3. $2 \ 5 \ 20 \rightarrow 10 \ 30 \ 35 \ 35 \ 25 \ 5 \ 0 \ 0$
4. $7 \ 8 \ 8 \rightarrow 10 \ 30 \ 35 \ 35 \ 25 \ 5 \ 8 \ 8$

Șirul final de intensități este: $[10, 30, 35, 35, 25, 5, 8, 8]$.

Suma totală este: $10 + 30 + 35 + 35 + 25 + 5 + 8 + 8 = 156$.

Exemplul 2

lumini.in

2
8 4
1 4 10
3 6 5
2 5 20
7 8 8

lumini.out

35

Explicație

Cerința 2 (Maximul):

Se aplică aceleași actualizări ca mai sus.

Șirul final de intensități este: $[10, 30, 35, 35, 25, 5, 8, 8]$.

Valoarea maximă din șir este $35$.