Its Sunday Morning once again.Harsh as usual wakes up late in the morning.But today his mom has got work for him. Harsh is supposed to paint the fence of his garden.His mom gives him K different paints and tells him to paint the fence such that no 2 adjacent planks in the fence have the same color. The fence is not circular that is first and last plank are not adjacent.She also gives him the cost of painting the ith plank of fence with the kth paint. Help him in finding the minimum cost in which he could paint the entire fence.

Input:

The first line contains 2 integers n and k where n indicates the number of planks in fence and k denotes the number of different paints.

This is followed by the n*k cost matrix which denotes the cost of painting each plank with each color.

Output:

The minimum cost associated with the job.

Constraints:

1<=k<=100

1<=n<=1000

1<=cost[i][j]<=1000