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

Cho M (M<= 100) hình tròn trên 1 bảng kích thước N*N  ô vuông(N <= 1000), Mỗi hình tròn có 1 bán kính R[i]-0.5 (R[i] nguyên, R[i] <= 100) và tâm nằm trên  trọng tâm của 1 ô vuông ở dòng x[i], cột y[i]. Các hình tròn có thể đè lên nhau và có hình có một phần diện tích nằm ngoài bảng. Yêu cầu: Tìm hình chữ nhật có diện tích lớn nhất nằm trên bảng mà không đè lên các hình tròn. Lưu ý: tất cả các dữ diệu input và output đều là số nguyên dương, kể cả kích thước và diện tích hình chữ nhật tìm được.

Ví dụ: Hình tròn có tâm (4;4), bán kính là 4 và phần bị phủ là phần màu đỏ.

Input

• Dòng đầu: số nguyên dương N và M.

• M dòng sau: Mỗi dòng ghi 3 số, lần lượt là tọa độ hàng, cột của ô chứa tâm, bán kính hình tròn.

Output

• Diện tích của hình chữ nhật tìm được, và phần diện tích bị các hình tròn phủ (không tính phần diện tính lan ra khỏi bảng).
  

Ví dụ

Input:
8 1
4 4 4


Output:
8 45