Color them all

All submissions for this problem are available.
You are given a square board of size n*n. A principal diagonal of a matrix is the diagonal connecting points (1,1) and (n,n). All the diagonals parallel to this diagonal (including itself) are called "Colorful diagonals". The given board has n*n small square boxes. Now you want to paint the board with some color. Some of the boxes are damaged beyond repair and you dont need to paint them.
 You have to start with one of the end diagonals. (i.e. diagonal joining (1,n) and (1,n) (upper side) or the diagonal joining (n,1) and (n,1) (lower side).
 You can not paint a diagonal unless one of its neighbour diagonals is painted.
 Every time the cost to paint a diagonal is (number of colorable boxes in the diagonal)*costA .
 Now at any point of time you can change the side of the matrix you are painting. But whenever you change the side cost for that diagonal becomes (number of colorable boxes in the diagonal)*costB.
 Remember that the cost becomes costB only for one diagonal after the change of the side.
 Now your task is to paint the matrix in minimum cost.
Input
First line will contain n (size of the square board), costA, costB. (Read the problem statement to know what is costA and costB).
Next n lines will contain n integers each representing the status of the box at (i , j) position. 1 represents the box to be colored and 0 represents the damaged box.
Output
Output a single line denoting the minimum cost to paint the matrix.
Constraints
 1 ≤ n ≤ 500
 1 ≤ costA , costB ≤ 2*10^{6}
Example
Input: 5 2 6 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 0 1 0 1 1 Output: 34
Author:  devamanyu 
Tags  devamanyu 
Date Added:  26102015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 