A soccer stadium is hosting a match between 2 rival teams with unruly fan bases, and need to put up a barrier to separate opposing hooligans. The barrier will occupy some seats, and the goal is to minimize the resulting reduction in ticket revenue. The seats are in a grid with m rows and n columns.

The completed barrier will extend from row 1 to m, and it will occupy a pair of adjacent seats in each row. There is no restriction on where in row 1 the barrier starts, and it is allowed to zig-zag left and right, but it can only shift by one seat per row. If the barrier occupies seats (i, j) and (i, j + 1) in row i, then the seats it occupies in row i + 1 must be either (i + 1, j 1) and (i + 1, j); (i + 1, j) and (i + 1, j + 1); or (i + 1, j + 1) and (i + 1, j + 2). (There is no requirement about balancing the number of seats on each side of the barrier. Eg, placing the entire barrier in the rightmost two columns is allowed.)

There is an array P[1..m][1..n] of positive prices for the seats. The cost of a complete barrier is the sum of the prices of the 2m seats it occupies.

Design a dynamic programming algorithm that computes the minimum possible cost of a complete barrier and runs in O(mn) time. Explain the reasoning behind your algorithm and running time analysis.