Nhằm hỗ trợ khả năng tự học cho sinh viên ngành CNTT, Khoa đã phát triển hệ thống hỗ trợ tự học và tự chấm các bài lập trình với tên gọi là IT-CODER (https://itcoder.hutech.edu.vn).

Để chuẩn bị cho kỳ thi Olympic quốc gia, CLB Olympic Tin học HUTECH đang đã sử dụng hệ thống ITCODER nhằm hỗ trợ chấm bài cho N đề thi khác nhau, giả sử rằng mỗi đề thi như vậy đều chỉ có đúng 2 bài tập. Mỗi bài tập đều sử dụng K test-case để hỗ trợ việc chấm điểm. Và mỗi test-case như vậy đều có độ khó được đo lường tương ứng là với 1 số nguyên dương từ 0-10^9.

Để có thể lựa chọn được chính xác các sinh viên có năng lực tốt, Ban chủ nhiệm CLB muốn tất cả N đề thi này có độ khó chênh lệch giữa 2 bài tập là ít nhất. Biết rằng độ khó của mỗi bài tập được tính bằng độ khó nhỏ nhất của tất cả các test-case đã thiết lập của bài tập đó.

Với số lượng 2 × N × K các độ khó sẽ sử dụng cho các đề thi, BCN CLB muốn phân bổ các đề thi sao cho sự chênh lệch độ khó giữa các bài tập trong đề thi không vượt quá ngưỡng d. Hãy giúp CLB phân bổ để tìm ra d nhỏ nhất có thể tạo được?

• Dòng 1: Dòng đầu tiên chứa hai số nguyên dương N và K test-case cách nhau bằng khoảng trắng.
• Dòng 2: Chứa 2 × N × K số nguyên p_i cách nhau bằng giá trị khoảng trắng, chỉ định độ khó cần sử dụng (1 ≤ p_i ≤ 10^9).

Hiển thị số nhỏ nhất d sao cho bạn có thể phân bổ các độ khó để đảm bảo sự chênh lệch giữa các đề thi không vượt quá d.

Ví dụ với N = 2 đề thi, mỗi bài tập có K = 3 test-case.

• Đề thi 1, có 2 bài tập trong đó có thể chọn:
  • Bài tập 1 sử dụng test-case có độ khó (1, 2, 5)
  • Bài tập 2 sử dụng test-case có độ khó (2, 4, 12). Độ chênh lệch độ khó của 2 bài tập này là 1.
• Đề thi 2, có 2 bài tập
  • Bài tập 1 sử dụng test-case có độ khó (6,8,9)
  • Bài tập 2 sử dụng test-case độ khó (7,10,11). Độ chênh lệch độ khó của 2 bài tập này là 1.

Như vậy có thể phân bổ tất cả các đề thi với d = 1.