THPT Chuyên Bến Tre

Bạn biết gì về trò chơi “Made in Việt Nam”  Flappy  Bird của tác giả Nguyễn Hà Đông? Hôm nay, chúng ta làm quen với phiên bản 2 của trò chơi này nhé.

Cho m hàng, mỗi hàng có n trụ đồng, khoảng cách giữa các trụ coi như không đáng kể. Trụ ở hàng i cột j có độ cao h_ij.

Chú chim Flappy xuất phát ở mặt đất (độ cao bằng 0) và dự trữ W đơn vị năng lượng, mỗi lần nhảy từ ví trí này đến vị trí khác chú bị tiêu hao một năng lượng đúng bằng độ cao của vị trí nhảy tới. Nhiệm vụ của chú chim ở phiên bản này là phải nhảy qua n trụ ở n cột khác nhau, mỗi lần chú chỉ có thể nhảy tới bất kỳ một trụ nào đó của cột kế tiếp.

Bờm và các bạn trong lớp mới tham gia và rất hứng thú với trò chơi này. Để chứng tỏ khả năng không “yếu kém”, Bờm muốn chú chim Flappy của mình nhảy từ trụ này tới trụ khác sao cho độ cao của các trụ không giảm và tổng độ cao các trụ là lớn nhất có thể.

Bạn hãy giúp Bờm chỉ ra hành trình của chú chim Fllapy.  

Input

• Dòng đầu chứa ba số n, m, W
• M dòng sau, dòng thứ I+1 (i=1..n), ghi n số h_i1, h_i2,…, h_in.

Output

• Nếu không tồn tại đáp số ghi ra số -1, ngược lại bạn ghi một số nguyên là tổng độ cao lớn nhất của các trụ chú chim Flappy nhảy qua.

Example

Input:
2 3 10
2 7 6
4 3 5

Output:
10

Input:
2 3 7
7 1 3
2  5 6
Output:
-1
* Giải thích ví dụ 1: (1,1)  ->   (2,2)   ->    (2,3)
* Chú ý: 
-         1≤W≤100 000
-         1≤M, N≤ 20
-         1≤Hij≤ 1 000
-         30% số test đầu có 1≤M, N≤ 10
-         30% số test tiếp theo có 1≤M, N≤ 15
-         40% số test cuối có 1≤M, N≤ 20