Với sự phổ biến ngày càng tăng của điện thoại thông minh, nhu cầu về mạng không dây của mọi người ngày càng lớn. Một thành phố nọ quyết định phủ sóng mạng không dây cho các địa điểm công cộng trong thành phố.

Giả sử bố cục của thành phố là dạng lưới tạo bởi $129$ con đường theo hướng đông-tây và $129$ con đường theo hướng bắc-nam song song tuyệt đối với nhau, và khoảng cách giữa hai con đường song song kề nhau luôn là hằng số $1$. Các con đường hướng đông-tây được đánh số lần lượt từ bắc xuống nam là $0,1,2 \dots 128$, các con đường hướng bắc-nam được đánh số lần lượt từ tây sang đông là $0,1,2 \dots 128$.

Đường hướng đông-tây và đường hướng bắc-nam giao nhau tạo thành các ngã tư, quy ước ngã tư tạo bởi con đường hướng bắc-nam số $x$ và con đường hướng đông-tây số $y$ có tọa độ là $(x, y)$. Tại một số ngã tư có một số lượng nhất định các địa điểm công cộng.

Do vấn đề ngân sách của chính quyền, chỉ có thể lắp đặt một bộ phát sóng mạng không dây cỡ lớn. Phạm vi phát sóng của bộ phát này là một hình vuông có tâm tại điểm đặt, cạnh dài $2d$. Phạm vi phát sóng bao gồm cả biên của hình vuông.

Hiện cơ quan chức năng chuẩn bị lắp đặt một bộ phát sóng không dây có tham số truyền sóng $d$, mong bạn giúp họ tìm ra ngã tư thích hợp trong thành phố để làm địa điểm lắp đặt, sao cho số địa điểm công cộng được phủ sóng là nhiều nhất.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $d$, biểu thị khoảng cách truyền sóng của bộ phát sóng không dây.

Dòng thứ hai chứa một số nguyên $n$, biểu thị số ngã tư có địa điểm công cộng.

$n$ dòng tiếp theo, mỗi dòng cho ba số nguyên $x, y, k$, cách nhau bởi một dấu cách, lần lượt là tọa độ ngã tư $(x, y)$ và số lượng địa điểm công cộng tại ngã tư đó. Mỗi tọa độ chỉ được cho một lần.

Dữ liệu ra

In ra một dòng chứa hai số nguyên, cách nhau bởi một dấu cách, lần lượt là số phương án chọn vị trí lắp đặt phủ sóng được nhiều địa điểm công cộng nhất, và số địa điểm công cộng nhiều nhất có thể phủ sóng được.

Ví dụ

Input

1
2
4 4 10
6 6 20

Output

1 30

Ghi chú

Phạm vi dữ liệu

Với $100\%$ dữ liệu, $1 \leq d \leq 20, 1 \leq n \leq 20, 0 \leq x \leq 128, 0 \leq y \leq 128, 0 < k \leq 10^6$.

Nguồn: NOIP 2014 bảng nâng cao, ngày 2 bài 1 (D2T1)