Avant-garde architecture
A developer in the capital has decided to construct a residential building designed by a renowned avant-garde architect. This building will feature cube-shaped apartments arranged in a whimsical structure. There are two main constraints: one from the architect and another from the laws of physics.
The architect requires that each floor consists of a connected sequence of cubes (separated floors were a trend in the 1990s). Additionally, at least one cube on each floor must be supported by a cube from the floor below. The first floor must be directly on the ground.
Beyond the physical constraints, the architect must also consider marketability. Since potential buyers are hesitant to invest in real estate, the building needs to offer something appealing, such as a great view from the windows. The developer's specialists have created a table that rates the attractiveness of the view from each possible apartment location. The goal is to maximize the total attractiveness of these views.
The example provided illustrates the attractiveness of the views and the optimal building configuration using 10 cubes.
Given the number of cubes and the table of window view attractiveness, your task is to select the best building design (maximizing total attractiveness) that adheres to the architect's requirements and the laws of physics.
Input
The first line of the input contains the natural numbers N, H, and W (1 ≤ H ≤ 30, 1 ≤ W ≤ 30, 1 ≤ N ≤ HW) — representing the number of available cubes, the maximum height, and the maximum width of the building. The following H lines each contain W natural numbers, indicating the attractiveness of placing an apartment at each position. Attractiveness values range from 1 to 100,000 inclusive.
Output
Output a single number — the maximum total attractiveness.