Giải bài trực tuyến

Ví dụ với tam giác đều bậc 1, 2, 3 và 4.

Từ hình trên ta có thể dễ dàng định nghĩa với tam giác đều bậc N (N <= 3000).

Ta sẽ đánh dấu các "hàng" của tam giác như sau.

N=5 với ô đỏ (2,2,3) và ô vàng (1,4,2)

Qui ước: để đọc vị trí một ô bất kì, ta đi ngược chiều kim đồng hồ từ đỉnh của tam giác và ghi nhận các "hàng" mà ô đó nằm trên (xem ví dụ ở trên).

Cho bảng tam giác bậc N. Hiện tại có 1 số ô đã có màu, các ô còn lại màu trắng.

Yêu cầu: Đếm số lượng tam giác màu trắng trên bảng.

Input

_ Dòng đầu tiên chứa số N và K là số bậc của tam giác và số ô đã tô màu (K <= N^2).

_ K dòng sau là bộ 3 các số a[i], b[i], c[i] thể hiện tọa độ của ô màu thứ i.

Output

_ Một dòng duy nhất là kết quả bài toán.

Example

Input:
5 2
2 2 3
1 4 2

Output:
31