JOI đang chơi bằng cách đóng đinh lên một tấm ván. Cậu xếp các đinh thành một tam giác đều, mỗi cạnh có \(N\) chiếc đinh. Hàng thứ \(a\) từ trên xuống (\(1\le a\le N\)) có \(a\) chiếc đinh. Chiếc đinh thứ \(b\) từ trái sang trong hàng đó (\(1\le b\le a\)) được ký hiệu là \((a,b)\).

Một tam giác đều có các đỉnh là những chiếc đinh được gọi là tam giác đều tốt nếu các cạnh của nó song song với các cạnh của tam giác lớn và nó có cùng hướng với tam giác lớn. Cụ thể, ba đỉnh của nó có dạng

trong đó \(1\le a<N\), \(1\le b\le a\) và \(1\le x\le N-a\).

JOI dùng dây chun để bao quanh các tam giác đều tốt. Một chiếc đinh được tính là được bao quanh nếu nằm bên trong hoặc trên biên của ít nhất một tam giác được dây chun bao quanh. Hình 2 minh họa cách đặt dây chun và được đặt trong phần giải thích Ví dụ 1.

Yêu cầu

Cho số đinh trên mỗi cạnh \(N\), số dây chun \(M\) và thông tin các tam giác mà \(M\) dây chun bao quanh. Hãy đếm số chiếc đinh được ít nhất một dây chun bao quanh. Mỗi chiếc đinh chỉ được đếm một lần, kể cả khi thuộc nhiều tam giác.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu tiên chứa hai số nguyên \(N,M\).
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(A_i,B_i,X_i\). Dây chun thứ \(i\) bao quanh tam giác có ba đỉnh \((A_i,B_i)\), \((A_i+X_i,B_i)\) và \((A_i+X_i,B_i+X_i)\).

Các số trên cùng một dòng được phân cách bởi dấu cách.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số chiếc đinh được ít nhất một dây chun bao quanh.

Ràng buộc

• \(2\le N\le5000\).
• \(1\le M\le500\,000\).
• \(1\le A_i<N\), \(1\le B_i\le A_i\), \(1\le X_i\le N-A_i\) với mọi \(1\le i\le M\).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

• \(30\%\) số điểm dành cho các dữ liệu thỏa mãn \(M\le10\,000\).

Ví dụ

5 2
2 2 1
2 1 3

12