Trapezoidal Paths

You are given a number trapezoid consisting of n rows. The first row contains m numbers, the second row contains m+1 numbers, and in general the i-th row contains m+i-1 numbers. From each number in the top row a path is started. From any cell you may move either diagonally left‐down or diagonally right‐down (that is, if you are at row i, column j then you can move to row i+1 at column j or j+1). In this way a path from the top to the bottom is formed. There will be exactly m such paths (one for each top cell).

There are three different cases regarding how these paths are allowed to overlap:

1. Disjoint Paths: The m paths must be vertex‐disjoint (i.e. no two paths may share any cell). In other words, if a cell is used by a path it cannot be used by another.
2. Node Intersection Only: The m paths may meet at nodes (cells) but they are not allowed to share an edge between cells. When summing values, if a cell is used by more than one path it is counted only once.
3. Full Intersection Allowed: The m paths are completely independent; if two or more paths pass through the same cell, the cell’s value is counted as many times as it appears.

Your task is, given the trapezoid and an integer t (which is 1, 2, or 3 indicating the above cases respectively), to select one valid path starting at each number in the top row (following the allowed moves) so as to maximize the total sum obtained from the cells along the paths. Note that for cases 1 and 2 the paths interact (by the restrictions and by the fact that cells which appear more than once are counted only once in case 2). In case 3 the paths are totally independent so the answer is simply the sum of the maximum sums of each individual path.

The movements can be described with the following recurrence. Let \(a_{i,j}\) be the value in the cell in row \(i\) (\(1 \le i \le n\)) and column \(j\) (columns are numbered starting from 1 in each row). From a cell \(a_{i,j}\), you may move to either \(a_{i+1,j}\) (left‐down) or \(a_{i+1,j+1}\) (right‐down), provided these cells exist. The three cases have the following additional restrictions on the positions chosen in each row:

• Case 1 (Disjoint): If the positions chosen in a row are \(p_1, p_2, ..., p_m\) corresponding to the paths starting at the first row, then \(p_1 < p_2 < \cdots < p_m\).
• Case 2 (Node Intersection Only): The positions must satisfy \(p_1 \le p_2 \le \cdots \le p_m\) (so paths may share a cell) and when summing the values in that row only distinct cells are counted.
• Case 3 (Full Intersection): Each path is taken independently (each cell is summed for every time it is visited).

Input Format:

• The first line contains three integers: \(n\), \(m\) and \(t\) (1 \(\leq\) \(t\) \(\leq\) 3).
• The next \(n\) lines describe the trapezoid. The \(i\)-th of these lines contains \(m+i-1\) space‐separated integers.

Output Format:

• Output a single integer: the maximum total sum possible considering the rules for case \(t\).

Sample Explanation:

For example, consider the following trapezoid with \(n=3\) and \(m=2\):

Row 1: 1 2
Row 2: 3 4 5
Row 3: 6 7 8 9

If \(t=1\) (disjoint paths) or \(t=2\) (node intersection only), one optimal solution yields a total sum of 29. However, if \(t=3\) (full intersection allowed), each path can be chosen independently and an optimal total sum is 27.

inputFormat

The input begins with a line containing three integers \(n\), \(m\) and \(t\) (\(t\) is 1, 2, or 3 as described above).

Then follow \(n\) lines. The \(i\)-th line contains \(m+i-1\) integers which represent the numbers in the trapezoid.

outputFormat

Output a single integer which is the maximum total sum obtainable by selecting one valid path from each top number according to case \(t\).

sample

3 2 1
1 2
3 4 5
6 7 8 9

29