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 ≤ i ≤ M) este descris prin trei valori: sti, dri și vali. Când acest efect este activat, intensitatea fiecărei lumini din intervalul [sti, dri] (inclusiv) crește cu valoarea vali. Acesta dorește să analizeze eficiența show-ului de lumini și are nevoie de ajutorul tău pentru a calcula două statistici.

Cerința

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 sti, dri și vali, 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 ≤ N, M ≤ 200 000
• 1 ≤ sti ≤ dri ≤ N
• 1 ≤ vali ≤ 1000
• Se garantează că intensitatea maximă (pentru cerința 2) nu va depăși 231 - 1.
• Se garantează că suma totală (pentru cerința 1) nu va depăși 263 - 1.

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 → 10 10 10 10 0 0 0 0
2. 3 6 5 → 10 10 15 15 5 5 0 0
3. 2 5 20 → 10 30 35 35 25 5 0 0
4. 7 8 8 → 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.