Nhân kỷ niệm 15 năm thành lập Khoa CNTT – Đại Học Giao thông Vận tải, Khoa tổ chức Hội khỏe Phù Đổng. Lớp CNTT1 K59 có rất đông sinh viên mỗi sinh viên có một chỉ số sức mạnh nào đó được chia thành N nhóm tham gia một nội dung thi đấu tập thể, Tichpx phải chọn đội tuyển cho lớp để thi đấu với các yêu cầu như sau:

1. Chọn trong N nhóm mỗi nhóm đúng một người tạo thành đội tuyển

2. Sức mạnh của đội tuyển là tổng các bình phương sức mạnh của từng người và lấy Modulo đi giá trị M cho trước

3. Xây dựng đội tuyển sao cho sức mạnh của đội tuyển là lớn nhất

Input

Dòng thứ nhất chứa N, M tương ứng là N (1<N<=8) số nhóm của lớp CNTT1K59 và M (1<M<=10000) là giá trị mà tổng bình phương sức mạnh phải modulo.

N dòng tiếp theo mỗi dòng là thông tin về từng nhóm gồm số thứ nhất k là số phần tử của nhóm đó (1<k<=8) theo sau là k số là chỉ số sức mạnh của từng sinh viên là số nguyên dương không vượt quá 1000

Output

Một số nguyên không âm duy nhất là chỉ số sức mạnh của đội tuyển

Ví dụ

Input

3   100     
3   5   6   2
2   4   3   
3   7   5   4

Output

94

Giải thích: Chọn các nhóm lần lượt là 6,3,7 kết quả \((6*6+3*3+7*7) mod 100=94\)