Olympic Tin học Sinh Viên

     Phân cụm là một bài toán có ý nghĩa ứng dụng quan trọng trong các lĩnh vực như học máy, khai phá dữ liệu, thu thập dữ liệu và đòi hỏi phân hoạch tập các điểm dữ liệu ra thành các nhóm sao cho các điểm trong cùng một nhóm là “gần nhau”  và “cách xa” các nhóm khác. Trong bài này chúng ta xét một dạng đơn giản của bài toán phân cụm.

  Cho tập gồm n đối tượng X = {x₁, x₂, ..., x_n}, khoảng cách d(x_i, x_j) giữa mọi cặp x_i, x_j và một số nguyên dương k (k ≤ n). Giả thiết là d(x_i, x_j) là các số nguyên dương, d(x_i, x_j) = d(x_j, x_i) và d(x_i, x_i) = 0, với mọi i = 1, 2, ..., n.

   Ta gọi một cách phân cụm là một  cách phân hoạch tập X ra thành k tập con khác rỗng (mỗi tập con như vậy được gọi là một cụm). Cho C = {C₁, C₂, ..., C_k}  là một cách phân cụm, ta gọi độ phân tách của cách phân cụm C (ký hiệu là r(C )) là giá trị nhỏ nhất trong số các khoảng cách giữa hai phần tử bất kỳ thuộc hai cụm khác nhau, nghĩa là

r(C ) = min {d(u,v): u thuộc C_p, v thuộc C_q , p # q }.

Yêu cầu: Tìm cách phân cụm với độ phân tách là lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên n và k. (2 ≤ K ≤ N ≤ 200)
• Dòng thứ i trong số n dòng tiếp theo ghi các số d(x_i, x₁), d(x_i, x₂), ..., d(x_i, x_n), i = 1, 2, ..., n. (d(x_i, x₁) ≤ 32767)
  

Output

    Độ tách phân cụm tìm được

Example

Input
4 3
0 1 2 3
1 0 2 3
2 2 0 3
3 3 3 0

Output:  
2