Có N trạm, đánh số từ 1 đến N. Ban đầu, tải bảo trì tại mỗi trạm bằng 0.

Có Q lịch bảo trì. Lịch thứ i tăng tải tại mọi trạm trong đoạn [l_i, r_i] thêm x_i đơn vị.

Sau khi thực hiện tất cả lịch, hãy tìm tải lớn nhất và chỉ số nhỏ nhất của một trạm đạt tải đó.

Dữ liệu vào

• Dòng đầu gồm hai số nguyên N và Q.
• Mỗi dòng trong Q dòng tiếp theo gồm ba số nguyên l_i, r_i, x_i, mô tả một lịch bảo trì.

Dữ liệu ra

In hai số nguyên: tải lớn nhất và chỉ số nhỏ nhất của trạm đạt tải lớn nhất.

Ràng buộc

• 1 ≤ N ≤ 200000.
• 0 ≤ Q ≤ 200000.
• 1 ≤ l_i ≤ r_i ≤ N.
• 1 ≤ x_i ≤ 10^9.

Phân nhóm điểm

1. (10 điểm) N, Q ≤ 2000.
2. (20 điểm) Mọi lịch đều tác động lên đúng một trạm (l_i = r_i).
3. (30 điểm) Với mọi lịch, l_i = 1 hoặc r_i = N.
4. (40 điểm) Không có ràng buộc nào khác.

Ví dụ

Input

5 4
1 4 2
2 3 3
1 1 3
4 5 3

Output

5 1

Sau khi áp dụng các lịch, tải tại các trạm lần lượt là 5, 5, 5, 5, 3. Tải lớn nhất là 5, đạt ở nhiều trạm; trạm có chỉ số nhỏ nhất là trạm 1.