Informatica Online Judge

  Nails [0605 / 025D]

Time Limit(Test case) : 3000(ms)
Number of users who solved : 58   Total Tried : 63


The Champion of this Problem (C++) : gs18103 - ms / 453byte
My Best Submission (C++) : N/A

[]

Background

경곽이는 나무판에 못을 박으며 놀고 있다. 아래 그림과 같이 경곽이는 한 변에 N개의 못을 정삼각형으로 박고 있다.

위로부터 a행째에는 a개의 못을 박는다. 그 중 왼쪽으로부터 b번째의 못을 (a,b)라고 한다.



못을 정점으로 하는 정삼각형이 각변이 전체의 정삼각형의 변과 평행하고, 전체의 정삼각형과 같은 방향일 때를 "좋은 정삼각형"이라고 한다.

즉, 좋은 정삼각형은 3개의 못 (a,b), (a+x,b), (a+x,b+x)를 정점으로 하는 정삼각형이다. (단, a,b,x는 1<=a<=N-1, 1<=b<=a, 1<=x<=N-1를 만족한다.)

경곽이는 고무밴드를 이용해서 좋은 정삼각형에 걸어보기로 했다.



정삼각형의 한 변을 이루는 못의 수 N과 경곽이가 가진 고무밴드의 수 M이 주어질 때, M개의 고무밴드로 좋은 정삼각형을 둘러싸는 방법이 주어질 때, 1개 이상의 고무밴드에 포함된 못의 수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 N, M이 공백으로 구분되어 입력된다.
둘 째줄 부터 M줄에 걸쳐서 좋은 정삼각형을 만들기 위한 고무밴드를 거는 위치에 대한 정보가 한 줄에 하나씩 입력된다.
정보는 Ai, Bi, Xi로 주어지며, 각 값은 (Ai,Bi), (Ai+X,Bi), (Ai+X,Bi+X)를 고무줄로 둘러싼다는 의미이다.

- 2 <= N <= 5,000
- 1 <= M <= 500,000

Output

고무밴드에 둘러쌓일 못의 수를 출력한다.

IO Example

입력
5 2
2 2 1
2 1 3

출력
12

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]