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\) và cột \(j\) có số nguyên dương \(a_{ij}\).

Bạn cần chọn hai vị trí khác nhau trong ma trận (tức là hai ô khác nhau), sao cho tổng hai giá trị tại đó không vượt quá \(S\) và là lớn nhất có thể.

Hãy in ra tổng lớn nhất tìm được. Nếu không thể chọn hai ô thỏa mãn, in ra \(-1\).

Input

• Dòng đầu chứa ba số nguyên dương \(m, n, S\).
• \(m\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên dương mô tả ma trận \(A\).

Output

In ra một số nguyên duy nhất là tổng lớn nhất của hai phần tử ở hai ô khác nhau, không vượt quá \(S\). Nếu không tồn tại, in ra \(-1\).

Giới hạn

• \(1 \le m, n \le 10^3\)
• \(1 \le S \le 2 \cdot 10^9\)
• \(1 \le a_{ij} \le 10^9\)

Scoring

• Subtask 1 (20%): \(m = 1\).
• Subtask 2 (30%): \(m, n \le 10^2\).
• Subtask 3 (50%): Không có ràng buộc gì thêm.

Input

1 4 17
1 9 7 11

Output

16

Input

2 4 7
1 2 2 3
3 3 7 2

Output

6

Input

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

Output

-1