Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

QBDISNEY - Thăm quan công viên Disney

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/qbdisney


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


Được gửi lên bởi:special_one
Ngày:2008-10-18
Thời gian chạy:0.100s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2009-03-17 18:09:12 Lê Ðôn Khuê
Nếu anh nhớ không nhầm thì bài này hồi trước anh cho IOICAMP. Anh viết thiếu 1 điều kiện rất quan trọng là đồ thị có dạng cây.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.