Digital Trapezoid Problem

Problem Source

Network Flow 24 Problems

Problem Description

Given a digital trapezoid made of $n$ rows of numbers, as shown in the figure below.

2 3
   3 4 5
  9 10 9 1
 1 1 10 1 1
1 1 10 12 1 1

The first row of the trapezoid has $m$ numbers. Starting from the $m$ numbers at the top of the trapezoid, at each number you may move down-left or down-right, forming a path from the top to the bottom of the trapezoid.

Compute, respectively, under the following three rules:

1. The $m$ paths from top to bottom are disjoint (no two paths share a vertex).
2. The $m$ paths from top to bottom may intersect only at number vertices.
3. The $m$ paths from top to bottom may intersect at number vertices or at edges.

Input Format

The first line contains $2$ positive integers $m, n(1\leq m, n\leq 20)$, meaning the first row of the trapezoid has $m$ numbers and there are $n$ rows in total. The following $n$ lines are the numbers of each row of the trapezoid.

The first row has $m$ numbers, the second row has $m+1$ numbers, and so on.

Output Format

Output the maximum total sum of numbers under rule 1, rule 2, and rule 3, one maximum total per line.

Sample Input

2 5
2 3
3 4 5
9 10 9 1
1 1 10 1 1
1 1 10 12 1 1

Sample Output

66
75
77

Constraints

$1\leq m, n\leq 20$.

Hint

• All three rules are classic maximum-cost maximum-flow problems on a layered network. Split each cell into an in- and out-node; rule 1 limits each cell to one path (capacity 1 on the out-node), rule 2 allows cell reuse but not edge reuse, and rule 3 allows everything (capacities set to infinity).