Chọn bạn nhảy

Câu lạc bộ khiêu vũ nhà trường sau thành lập có \(m\) bạn nam được đánh số từ \(1\) đến \(m\) và \(n\) bạn nữ được đánh số từ \(1\) đến \(n\) đăng ký tham gia. Bạn nam thứ \(i\) có chiều cao \(a_i\) (\(i = 1, 2, \ldots, m\)), bạn nữ thứ \(j\) có chiều cao \(b_j\) (\(j = 1, 2, \ldots, n\)).

Việc bố trí cặp nhảy trong các đội hình là rất quan trọng, câu lạc bộ cần chọn một đội hình gồm \(k\) cặp bạn nhảy. Mỗi cặp nhảy có đúng một bạn nam và một bạn nữ, mỗi bạn tham gia nhiều nhất một cặp. Chỉ số phù hợp của một cặp bạn nhảy là chênh lệch chiều cao của hai người, chỉ số phù hợp của cả đội hình bằng chỉ số phù hợp của cặp bạn nhảy lớn nhất.

Yêu cầu: Hãy chọn một đội hình gồm \(k\) cặp bạn nhảy sao cho chỉ số phù hợp của đội hình là nhỏ nhất.

Input

• Dòng đầu tiên chứa ba số nguyên dương \(m, n, k\) (\(m, n \le 10^5\), \(k \le \min(m, n)\)).

• Dòng \(2\) chứa \(m\) số nguyên dương \(a_1, a_2, \ldots, a_m\) (\(a_i \le 10^9\)).

• Dòng \(3\) chứa \(n\) số nguyên dương \(b_1, b_2, \ldots, b_n\) (\(b_j \le 10^9\)).

Ràng buộc:

• Có \(30\%\) số test ứng với \(30\%\) số điểm thỏa mãn: \(m, n \le 10^3\), \(k = 1\).

• \(30\%\) số test ứng với \(30\%\) số điểm thỏa mãn: \(m, n \le 10^5\), \(k = 1\).

• \(40\%\) số test còn lại ứng với \(40\%\) số điểm không có ràng buộc gì thêm.

Output

Ghi ra một số nguyên duy nhất là chỉ số phù hợp của đội hình theo phương án được chọn.

Example 1

Input:

4 5 3
1 2 3 4
2 2 1 4 5

Output:

0

Example 2

Input:

4 5 4
1 2 3 4
2 2 1 4 5

Output:

1

Note

Ở ví dụ thứ nhất, ghép bạn nam cao \(1\) với bạn nữ cao \(1\), bạn nam cao \(2\) với bạn nữ cao \(2\), bạn nam cao \(4\) với bạn nữ cao \(4\): cả \(3\) cặp đều có chênh lệch \(0\).

Ở ví dụ thứ hai cần \(4\) cặp, bạn nam cao \(3\) phải ghép với một bạn nữ cao \(2\) (hoặc \(4\)), chênh lệch \(1\), nên đáp án là \(1\).