Maximum benefit path P32049


Statement
 

pdf   zip

html

Consider an r × c board, where every cell has a positive value. You are located at the top left cell, and you must go to the bottom right cell, never leaving the board. Every step must be made down or to the right, with one exception: you can make j chess knight jumps (each, in any of the eight possible ways). Every time you pass by a cell you accumulate its value. Optimize the benefit.

Input

Input consists of several cases. Every case begins with r, c and j, followed by r rows with c natural numbers between 1 and 105. Assume that both r and c are between 3 and 100, and that j is between 0 and 100.

Output

For every case, print the maximum possible benefit.

Public test cases
  • Input

    3 5 0
     2 20 20  3 20
     3  1  1  1  1
    50  2  5  1  4
    
    3 5 1
     2 20 20  3 20
     3  1  1  1  1
    50  2  5  1  4
    

    Output

    70
    130
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++