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

样例下载

题目描述

有一个 2×N 的棋盘，其中有 M 个格子是坏格子，其它是好格子。

现在让你恰好使用 K 个矩形将棋盘上的坏格子覆盖住，每个矩形的大小和覆盖区域由你任意指定。你需要使得 M 个坏格子都被覆盖住，但被覆盖住的好格子数量尽量少。

问：保证所有坏格子均被覆盖的前提下，最少覆盖多少个好格子？

输入格式

第一行：三个整数 $N, M, K$

接下来 $M$ 行，每行两个整数 $x, y$, 表示第 $x$ 行第 $y$ 列的格子为坏格子（$x \in \{1,2\}, 1 ≤ y ≤ N$）。

输出格式

一个整数，表示答案。

样例输入

10 6 2
1 2
1 3
2 3
1 4
1 7
2 7

样例输出

2

数据范围

$10\%$ 的数据，$1 ≤ N ≤ 10$，$1 ≤ K ≤ M ≤ 10$。

$40\%$ 的数据，$1 ≤ N ≤ 100$，$1 ≤ K ≤ M ≤ 10$。

$100\%$ 的数据，$1 ≤ N ≤ 2×10^7$，$1 ≤ K ≤ M ≤ 10^3$。