Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PT_KT1B2 - Búng chim

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 hij.

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ố hi1, hi2,…, hin.

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


Được gửi lên bởi:Vương Trung Hiếu Nghĩa
Ngày:2014-09-16
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC MAWK BC C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG DART ELIXIR FANTOM FORTH GRV JULIA KTLN OBJC OCT PAS-FPC PROLOG PYPY3 R RACKET CHICKEN SQLITE SWIFT UNLAMBDA
Nguồn bài:Đề Phú Thọ

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.