Hogathon is the most exciting event of Bitotsav.
There are K teams participating in this event. Each team needs to send 2 members for this event. This time only cupcakes are available for the participants. There are N * N cupcakes in total which are arranged in the shape of a square matrix, a cupcake in each cell of the matrix
Let the leftmost cell in the top row be denoted by (1,1) and the rightmost cell in the bottom row be (N,N). The rules of the event are as follows :
1) The 2 members from team have to eat a cupcake each.
2) The cupcakes chosen by the 2 members need to be adjacent i.e they can be one of the below combinations :
3) No cupcake can be chosen more than once i.e a cupcake once chosen is removed from the matrix.
Each cupcake has a sweetness factor associated with it. Your task is to minimize the sum of the sweetness of cupcakes remaining in the matrix after the turn of K teams.
- The first line of input contains two integers N and K denoting the number of rows of matrix and number of teams respectively.
- The next N lines contain N space separated integers each describing the sweetness factor of the cupcakes
Print the minimum sum of sweetness factor of cupcakes remaining in the matrix after the K teams have consumed the cupcakes
- 1 ≤ N ≤ 3000
- 1 ≤ K ≤ 8
- 0 ≤ Sweetness Factor ≤ 1000
Input: 3 1 2 7 6 9 5 1 4 3 8 Output: 31
Example case 1. Team 1 chooses the cupcakes present in (2,1) and (2,2)
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions