Codeforces Round 815 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

constructive algorithms

data structures

greedy

implementation

math

*2700

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Misha and Paintings

time limit per test

3.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMisha has a square $$$n \times n$$$ matrix, where the number in row $$$i$$$ and column $$$j$$$ is equal to $$$a_{i, j}$$$. Misha wants to modify the matrix to contain exactly $$$k$$$ distinct integers. To achieve this goal, Misha can perform the following operation zero or more times:

- choose any square submatrix of the matrix (you choose $$$(x_1,y_1)$$$, $$$(x_2,y_2)$$$, such that $$$x_1 \leq x_2$$$, $$$y_1 \leq y_2$$$, $$$x_2 - x_1 = y_2 - y_1$$$, then submatrix is a set of cells with coordinates $$$(x, y)$$$, such that $$$x_1 \leq x \leq x_2$$$, $$$y_1 \leq y \leq y_2$$$),
- choose an integer $$$k$$$, where $$$1 \leq k \leq n^2$$$,
- replace all integers in the submatrix with $$$k$$$.

Please find the minimum number of operations that Misha needs to achieve his goal.

Input

The first input line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 500, 1 \leq k \leq n^2$$$) — the size of the matrix and the desired amount of distinct elements in the matrix.

Then $$$n$$$ lines follows. The $$$i$$$-th of them contains $$$n$$$ integers $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}$$$ ($$$1 \leq a_{i,j} \leq n^2$$$) — the elements of the $$$i$$$-th row of the matrix.

Output

Output one integer — the minimum number of operations required.

Examples

Input

3 4 1 1 1 1 1 2 3 4 5

Output

1

Input

3 2 2 1 3 2 1 1 3 1 2

Output

2

Input

3 3 1 1 1 1 1 2 2 2 2

Output

1

Input

3 2 1 1 1 1 2 1 2 2 2

Output

0

Note

In the first test case the answer is $$$1$$$, because one can change the value in the bottom right corner of the matrix to $$$1$$$. The resulting matrix can be found below:

1 | 1 | 1 |

1 | 1 | 2 |

3 | 4 | 1 |

In the second test case the answer is $$$2$$$. First, one can change the entire matrix to contain only $$$1$$$s, and the change the value of any single cell to $$$2$$$. One of the possible resulting matrices is displayed below:

1 | 1 | 1 |

1 | 1 | 1 |

1 | 1 | 2 |

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/13/2024 06:41:02 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|