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

Công viên DISNEYLAND là một công viên hiện đại mới được xây dựng ở ngoại ô Hà Nội để dành riêng cho trẻ em. Công viên này có N điểm vui chơi được đánh số từ 1 đến N. Các điểm vui chơi được nối liền với nhau bằng các đoạn đường hai chiều theo hướng Bắc – Nam, hoặc Đông – Tây. Các điểm vui chơi nằm ở giao của hai con đường. Khoảng cách giữa hai điểm vui chơi liên tiếp cách đều nhau.

Bé Bi được bố mẹ cho phép đến công viên chơi trong một ngày. Vì công viên quá rộng lớn và hấp dẫn nên bé Bi muốn lựa chọn một con đường đi qua một số điểm vui chơi sao cho không có điểm vui chơi nào đi qua 2 lần. Vì bố mẹ sợ bé Bi bị lạc, nên bố mẹ chỉ cho phép bé đi trên đoạn đường gồm không quá K ngã rẽ (không được đổi hướng quá K lần). Biết rằng độ dài đoạn đường nối hai điểm kề nhau có giá trị là 1. Bạn hãy giúp bố mẹ bé tính xem, đoạn đường dài nhất thỏa mãn điều kiện đó có độ dài là bao nhiêu, và có bao nhiêu đoạn đường thỏa mãn điều kiện đó. Lưu ý rằng công viên rất hiện đại nên có cả hệ thống cầu vượt và hầm chui. Chính vì vậy sẽ có những trường hợp như test ví dụ thứ hai dưới đây (các đỉnh ở cùng tọa độ nhưng hoàn toàn phân biệt với nhau).

Input

Dòng thứ nhất ghi 2 số nguyên dương N và K là số điểm vui chơi và số ngã rẽ nhiều nhất. ( 0 ≤ K < N ≤ 10000 )

Dòng thứ i trong N dòng tiếp theo ghi 4 số nguyên mô tả thông tin về điểm vui chơi thứ i. Bốn số nguyên là L, D, R, U là điểm vui chơi nằm bên trái, dưới, phải, trên điểm vui chơi thứ i. (Nếu có số bằng 0 tương ứng với phía đó không có điểm vui chơi nào).

Output

Gồm 2 số nguyên S và P trong đó S là độ dài đường đi dài nhất và P là số đường đi có độ dài là S.

Example

Input:
12 4
0 2 3 4
0 0 0 1
1 0 0 0
5 1 0 0
6 0 4 0
0 7 5 0
8 0 9 6
10 11 7 12
7 0 0 0
0 0 8 0
0 0 0 8
0 8 0 0
Output:
7 4



Input:
5 2
0 0 2 0
1 3 0 0
4 0 0 2
0 0 3 5
0 4 0 0
Output:
3 2