Cerința

În clasa a IX-a A sunt M elevi, numerotați de la 1 la M și fiecare are un număr preferat P. Plictisiți de ora de informatică, au inventat următorul joc:

• pe o foaie de matematică desenează o tablă de joc de dimensiune N, formată din N linii și N coloane, numerotate de la 1 la N; fiecare linie și fiecare coloană are câte N pătrățele
• fiecare elev alege un pătrățel și desenează un X centrat în pătrățelul ales, fiecare din cele 4 laturi având cel mult P pătrățele desenate, fără a ieși de pe tabla de joc (să nu mâzgălească banca!!).
• icsurile desenate de elevi se pot suprapune.

În figura de mai jos este reprezentat un X desenat de elevul care alege pătrățelul de coordonate i j și preferă numărul 3.

Cunoscând dimensiunea N a tablei de joc, numărul M de elevi, coordonatele alese de fiecare elev și numărul preferat al fiecărui elev, determinați câte pătrățele de pe tablă rămân nedesenate.

Date de intrare

Programul citește de la tastatură numărul N M, iar apoi M triplete i j p, reprezentând coordonatele pătrățelului ales și numărul preferat de fiecare elev.

Date de ieșire

Programul va afișa pe ecran numărul de pătrățele nedesenate.

Restricții și precizări

• 1 ≤ N ≤ 1000
• 1 ≤ M ≤ 100000
• 1 ≤ i,j ≤ N
• 0 ≤ p ≤ N/2

Exemplu

Intrare

10 5
1 2 1
6 6 3
7 3 2
2 5 2
9 8 3

Ieșire

62

Explicație

Exemplul corespunde tablei de joc de mai jos. Unele pătrățele au fost desenate de mai multe ori.

#include <bits/stdc++.h>
using namespace std;
int a[1001][1001];
int di[]={-1, -1, 1, 1};
int dj[]={-1, 1, -1, 1};
int main()
{
    int n , s , cnt=0 , i , j , nr;
    cin >> n >> s;
    for(int h = 1; h <= s; h++)
    {
        cin >> i >> j >> nr;
        a[i][j] = 1;
        for(int k = 1; k <= nr; k++)
            for(int q = 0; q < 4; q++)
            {
                int i1 = i + k * di[q];
                int j1 = j + k * dj[q];
                if(i1 >= 1 && i1 <= n && j1 >= 1 && j1 <= n)
                    a[i1][j1] = 1;
            }
    }
    for(int i = 1; i <= n; i++)
       for(int j = 1; j <= n; j++)
        if(a[i][j] == 1)
            cnt++;
    cout << n * n - cnt;
    return 0;
}