Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Nước Graphia đang có chiến tranh. Đất nước này có nhiều thành phố. Các thành phố nối với nhau bởi các đường cao tốc. Mỗi thành phố có một số đội quân đang đóng ở đó. Bộ Quốc phòng Graphia a biết rằng để bảo vệ bất cứ thành phố nào thì cần số đội quân là K. Một thành phố được bảo vệ bởi các đội quân đóng tại đó và các đội quân đóng ở các thành phố có đường trực tiếp với thành phố đó. Với giả sử quân địch chỉ tấn công một thành phố tại một thời điểm.

Tuy nhiên, nếu một thành phố không thể được bảo vệ thì Bộ Quốc phòng phải xem như các đội quân ở đó sẽ bị bắt và không hỗ trợ được gì cho phòng thủ các thành phố khác. Trong trường hợp sau, với K=10, thành phố C có thể bị thất bại (sau khi dịch chiếm các thành phố có số quân là 4 ở xung quanh thành phố C). 

Người ta muốn tìm ra trái tim của đất nước là nhóm lớn nhất các thành phố có thể bảo vệ lẫn nhau, ngay cả khi các thành phố khác bị thất bại. 

Input

Có nhiều bộ test, mỗi bộ test gồm

• Dòng 1 ghi 2 số N và K (3<=N<=1000; 0<=K<N).
• N dòng tiếp theo mô tả các thành phố (đánh số từ 0): gồm số đội quân T đang đóng ở đó (0<=T<=10000) và số các thành phố nối với nó – M. Sau đó là M số nguyên cho biết các thành phố được nối với nó. Các đường là hai chiều và không có hai đường nào nối cùng một cặp thành phố với nhau, không có thành phố nào có đường đi đến chính nó.
• Bộ test cuối cùng chứa 2 số 0

Output

Với mỗi bộ test, ghi ra màn hình 2 số nguyên: số thành phố trong vùng trái tim của đất nước và số đội quân trong vùng trái tim đó

Example

Input:
4 900
100 2 1 2
200 2 0 3
500 2 0 3
1000 2 1 2
4 900
100 3 1 2 3
200 3 0 3 2
500 3 1 3 0
1000 3 2 1 0
0 0

Output:
3 1700
4 1800