该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[USACO05NOV] Asteroids G

题目描述

贝茜想在 $N\times N$ 的网格中驾驶她的宇宙飞船。网格中有 $K$ 个小行星。要使驾驶过程愉快，就必须把这些小行星全部消除。

贝茜有一个武器，可以以一个单位代价消除一行或一列的全部小行星。贝茜想问你，要把所有小行星都消除的最小代价是多少。

输入格式

第一行两个整数 $N,K$。

接下来 $K$ 行，每行输入 $x_i,y_i$，表示第 $i$ 个小行星在网格的坐标。

输出格式

一行一个整数，表示把所有小行星消除的最小代价。

样例 #1

样例输入 #1

3 4
1 1
1 3
2 2
3 2

样例输出 #1

2

提示

样例解释：

样例的图为（X 为小行星）：

X.X
.X.
.X.

贝茜可以分别消除第一行和第二列的小行星。

数据范围：

对于 $100\%$ 的数据，$1 \leq N \leq 500$，$1 \leq K \leq N \times N$。