AlgoLiga 2018

Jaś od zawsze uważał, że najlepiej szacuje, jaka część całego obszaru jest pokolorowana. Kiedy jego mama maluje ścianę czy myje podłogę, Jaś zawsze trafnie ocenia, jaką część pracy ma już za sobą. Nikt nigdy nie podważał, że jest on w tym najlepszy, aż do dzisiaj. W tym celu postanowiono zrobić zawody.

Mamy planszę w kształcie piramidy zbudowanej z pól w kształcie jednakowych rombów (na rysunku obok plansza o rozmiarze 5). Jury konkursu zamalowało część planszy, wybierając do tego wiele mniejszych piramid zawierających się w planszy. Należy oszacować, ile jednostkowych rombów jest pomalowanych. Powstał jednak problem - nasi zawodnicy szybko szacują, a "ręczne" zliczanie trwa bardzo długo. Aby przyśpieszyć pracę, organizator poprosił Cię o napisanie programu, który wyręczy jurorów w pracy. Jako dane wejściowe dostaniesz rozmiar planszy i parametry każdej z zamalowanych piramid w postaci trzech liczb a, b i k. Dzięki tym liczbom wiemy, że zamalowana piramida ma wierzchołek w punkcie (a,b), a skrajne romby w podstawie mają współrzędne (a+k,b) i (a+k,b+k).

Wejście:

W pierwszej linii dwie liczby N, T oznaczające odpowiednio rozmiar planszy i liczbę zamalowanych piramid.
W następnych T liniach są po trzy liczby a b k opisujące kolejne piramidy.

Ograniczenia: N ≤ 5000, T ≤ 300 000,  b ≤ a ≤ N, 0 ≤ k ≤ N-a

Wyjście:

W pierwszym i jedynym wierszu należy wypisać liczbę pomalowanych jednostkowych rombów.

Przykład:

Wejście:
5 2
2 1 1
2 2 2

Wyjście:
8

Rysunek do przykładu: