Paint House - Many Colors

easy

1. You are given a number n and a number k separated by a space, representing the number of houses and number of colors.
2. In the next n rows, you are given k space separated numbers representing the cost of painting nth house with one of the k colors.
3. You are required to calculate and print the minimum cost of painting all houses without painting any consecutive house with same color.

Input Format

A number n n1-0th n1-1st n1-2nd .. n1-kth n2-0th n2-1st n2-2nd .. n2-kth .. n number of elements

Output Format

A number representing the minimum cost of painting all houses without painting any consecutive house with same color.

Constraints

1 &lt;= n &lt;= 1000
1 &lt;= k &lt;= 10
0 &lt;= n1-0th, n1-1st, .. &lt;= 1000

Notice

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

Example

Input

Output

Maximum Sum Non Adjacent Elements

Tiling With 2 * 1 Tiles