Avant-garde architecture#584
A developer in the capital has decided to construct a residential building designed by a renowned avant-garde architect. This building will consist of cube-shaped apartments and have an unusual design. There are two main constraints: one set by the architect and another by the laws of physics.
The architect requires that each floor is a connected sequence of cubes (separate floors are a fashion of the 1990s). Also, at least one cube on each floor must be directly supported by a cube from the floor below. The first floor must be on the ground.
In addition to the laws of physics, the need to sell the building is also a limitation, since buyers are hesitant to purchase real estate and must be attracted by something, for example, by the view from the windows. Specialists from the developer's company have created a table showing the attractiveness of the view from each possible apartment location. The goal is to maximize the total attractiveness of the views.
The given example shows the attractiveness values and the best building for cubes in this case.
Given the number of cubes and the attractiveness table, choose the best design (with maximum total attractiveness), following the architect's requirements and the laws of physics.
The first line contains the natural numbers , , and (1 \le H \le 30, 1 \le W \le 30, 1 \le N \le HW) — the number of available cubes, the maximum height, and the maximum width of the building. The next lines each contain natural numbers, representing the attractiveness for each apartment location. Attractiveness is measured from to inclusive.
Print one number — the maximum total attractiveness.
Example 1