Kỳ thi Olympic truyền thống 30 tháng 4 quy tụ ~N~ đoàn thí sinh đến từ các trường khác nhau trên khắp cả nước. Mỗi đoàn bao gồm ~C~ thí sinh, trong đó thí sinh thứ ~j~ ở đoàn thứ ~i~ có chỉ số kỹ năng là ~A_{ij}~.

Ban tổ chức muốn chọn ra một đội gồm ~N~ thí sinh, mỗi đoàn một thí sinh để chơi một trò chơi giao lưu. Để mỗi thí sinh thể hiện hết khả năng của mình, ban tổ chức muốn nhóm được chọn gồm các thí sinh có chỉ số kỹ năng càng tương đồng càng tốt. Cụ thể, ban tổ chức muốn sự chênh lệch chỉ số kỹ năng của thí sinh có chỉ số kỹ năng cao nhất và thấp nhất trong đội được chọn là nhỏ nhất có thể. Lê được ban tổ chức giao nhiệm vụ lựa chọn thí sinh cho trò chơi, nhưng vì số lượng thí sinh quá lớn nên cậu cũng không biết phải làm thế nào.

Yêu cầu: Bạn hãy giúp Lê chọn ra đội chơi một cách tối ưu nhất.

Input

• Dòng đầu gồm hai số nguyên dương ~N~ và ~C~ ~(1 \le N,C \le 1500)~.

• Dòng thứ ~i~ trong số ~N~ dòng tiếp theo gồm ~C~ số nguyên dương ~A_{i1}, A_{i2}, \dots, A_{iC}~ ~(1 \le A_{ij} \le 10^9)~.

Output

Gồm duy nhất một số là chênh lệch chỉ số kỹ năng nhỏ nhất tìm được.

Scoring

Sample Input 1

2 3
3 1 8
5 6 7

Sample Output 1

1

Sample Input 2

3 3
3 1 4
2 7 16
9 8 10

Sample Output 2

4

Notes

Trong ví dụ thứ nhất, Lê có thể chọn thí sinh thứ ba của mỗi đoàn để tạo thành một đội gồm các thí sinh có chỉ số kỹ năng lần lượt là ~7~ và ~8~. Chênh lệch chỉ số kỹ năng trong trường hợp này là ~1~.

Trong ví dụ thứ hai, Lê có thể chọn thí sinh thứ ba của đoàn thứ nhất và thí sinh thứ hai của đoàn thứ hai và thứ ba để tạo thành một đội gồm các thí sinh có chỉ số kỹ năng lần lượt là ~4,7,8~. Chênh lệch chỉ số kỹ năng trong trường hợp này là ~4~.