All submissions for this problem are available.A school runs for $N$ days and each day consists of classes of $M$ different subjects. Fees for the courses change each day ie $A(i, j)$ is the fee for jth subject on ith day. Chef is poor and wants to attend one class each day such that he does not have to attend the same subject for consecutive days and the total cost is minimum. Find the minimum possible total fees chef will pay if he attends classes each day. ###Input: First line contains $N$ and $M$. Next $N$ lines each of them has $M$ integers describing fees for the courses on that day. $A(i, j)$ is the fee for jth subject on ith day. ###Output: Output in a single integer, minimum possible total fees chef will pay if he attends classes each day. ###Constraints: All values in input are integers. - $1 \leq N \leq 100000$ - $2 \leq M \leq 10$ - $1 \leq A(i, j) \leq 10000$ ###Subtasks: for 30 points: - $1 \leq N \leq 10$ - $2 \leq M \leq 5$ for 70 points: original constraints. ###Sample Input: 4 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ###Sample Output: 30 ###EXPLANATION: Chef will attend 1st class on 1st day, 2nd class on 2nd day, 1st class on 3rd day and ,2nd class on 4th day , minimum possible total fees $(1 + 6 + 9 + 14) = 30$. Note that $(2+5+10+13) = 30$ is also a valid solution.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.