Tìm cặp số

Cho số nguyên dương \(S\) và ma trận \(A\) có \(m\) hàng, \(n\) cột. Ô giao giữa hàng \(i\) (\(i = 1..m\)) và cột \(j\) (\(j = 1..n\)) có số nguyên dương \(a_{ij}\) (\(a_{ij} \le 10^9\)).

Yêu cầu: Tìm tổng lớn nhất của \(2\) phần tử ở \(2\) vị trí khác nhau trong ma trận \(A\) sao cho tổng này không lớn hơn số nguyên dương \(S\).

Input

Dữ liệu vào:có thông tin sau:

• Dòng đầu tiên có \(3\) số nguyên dương \(m, n, S\) (\(m, n \le 10^3\); \(S \le 2 \times 10^9\));

• \(m\) dòng tiếp theo, mỗi dòng có \(n\) số nguyên dương không vượt quá \(10^9\).
  Các số trên cùng một dòng trong dữ liệu được viết cách nhau bởi dấu cách trống.

Ràng buộc:

• Subtask 1 (\(20\%\) số điểm): Dữ liệu vào có \(m = 1\).

• Subtask 2 (\(30\%\) số điểm): Dữ liệu vào có \(m, n \le 10^2\).

• Subtask 3 (\(50\%\) số điểm): Không có ràng buộc nào thêm.

Output

In ra kết quả một dòng là tổng lớn nhất tìm được theo yêu cầu. Nếu không tìm được \(2\) phần tử theo yêu cầu thì in ra \(-1\).

Example 1

Input:

1 4 17
1 9 7 11

Output:

16

Example 2

Input:

2 4 7
1 2 2 3
3 3 7 2

Output:

6

Example 3

Input:

3 4 10
6 7 8 9
5 6 7 8
9 8 8 7

Output:

-1

Note

Ở ví dụ thứ ba, hai phần tử nhỏ nhất là \(5\) và \(6\) có tổng \(11 > 10\) nên không có cặp thỏa mãn.