Bài 3. TÌM CẶP SỐ

Cho số nguyên dương S và một ma trận A có m hàng, n cột. Ô giao giữa hàng i và cột j chứa số nguyên dương aᵢⱼ.

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

Nếu không tồn tại hai phần tử thỏa mãn yêu cầu, in ra -1.

INPUT

• Dòng đầu tiên chứa ba số nguyên dương m, n, S
  (m, n ≤ 10³; S ≤ 2 × 10⁹);
• m dòng tiếp theo, mỗi dòng chứa n số nguyên dương aᵢⱼ
  (aᵢⱼ ≤ 10⁹).

Các số trên cùng một dòng được viết cách nhau bởi dấu cách.

OUTPUT

Ghi ra một số nguyên duy nhất là tổng lớn nhất không vượt quá S của hai phần tử ở hai vị trí khác nhau.

Nếu không tìm được hai phần tử thỏa mãn yêu cầu, ghi -1.

Ràng buộc

Subtask 1 — 20% : m = 1.

Subtask 2 — 30% : m, n ≤ 10².

Subtask 3 — 50% : Không có ràng buộc bổ sung.

Ví dụ

Sample Input 1

1 4 17
1 9 7 11

Sample Output 1

16

Sample Input 2

2 4 7
1 2 2 3
3 3 7 2

Sample Output 2

6

Sample Input 3

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

Sample Output 3

-1