Didel a învățat astăzi la matematică ce este un dreptunghi. El a definit numărul special al unei perechi astfel: A desenat un dreptunghi de lungime și lățime . Numărul special va fi numărul de pătrate (de latură naturală, mai mare ca ) incluse în dreptunghiul desenat.
În figura de mai sus, sunt pătrate de latură și pătrat de latură . Deci numărul special al perechii va fi .
Cerință
Se dă un șir de numere întregi, . Se dau actualizări de forma : Adaugă la numărul special al perechii . După toate actualizările, să se afle maximul din șirul .
Date de intrare
Pe prima linie a fișierului de intrare special.in
se găsesc două numere întregi, și , reprezentând numărul de elemente din șir și numărul de actualizări. Pe a doua linie se vor găsi numere întregi, separate prin câte un spațiu, . Pe următoarele linii se vor găsi cele actualizări (pe a -a linie se vor găsi numerele (separate prin câte un spațiu), reprezentând forma celei de a -a actualizare).
Date de ieșire
Pe prima linie a fișierului de ieșire special.out
se va găsi un singur întreg, maximul din șirul .
Restricții și precizări
- (pentru )
- La finalul tuturor actualizărilor, .
- (pentru )
- (pentru )
Exemplu
special.in
5 4
1 2 3 4 5
1 4 6 7
1 2 3 4
4 5 2 1
2 4 5 1
special.out
80
Explicație
Șirul devine: . Maximul este .