Pepe the frog needs to jump across a river while only stepping on some stones! He needs to jump from column ~1~ to column ~N~ (left to right in the input). Rock ~i~ means the rock on row ~i~. However, jumping from row ~i~ to ~j~ takes ~(i-j)^2~ time.
The first line of the input contains two integers, ~N~ and ~C~, the number of columns and the number of positions of rocks.
Each subsequent ~C~ lines of the input contains of a string of ~N~
1 on line ~i~ (starting from 2nd line) on column ~j~ (both 0-indexed) indicates the rock ~j~ is present in column ~i~, a
0 indicates that rock ~j~ is not present.
Output the minimum amount of time taken to jump to the end.
You are guaranteed there is at least one possible way to jump to the end.
Subtask 1 (10%) ~1\le N,C\le7~
Subtask 2 (5%) ~1\le N,C\le100~
Subtask 3 (20%) ~1\le N,C\le500~
Subtask 4 (20%) ~1\le N,C\le750~
Subtask 5 (45%) ~1\le N,C\le2000~
Sample Input 1
5 3 11100 00011 11111
Sample Output 1
Sample Input 1 Explanation
You don't need to jump, just use rock 3 throughout.
Sample Input 2
5 5 10000 01000 00100 00010 00001
Sample Output 2
Sample Input 2 Explanation
Start from rock 0, change to rock 1, change to rock 2, etc. Each of them takes 1 time because they are adjacent.