요청

크기가 모두 같은 객체들의 모임과, 최대 $K$개의 객체를 담을 수 있는 캐시, 그리고 $N$개의 요청으로 이루어진 수열이 주어진다. 각 요청은 하나의 객체를 요구하며, 그 객체가 언제까지(그 시각 포함) 유효한지를 나타내는 만료 시각을 함께 가진다.

시각은 $1$에서 시작하여 매 요청마다 $1$씩 증가하므로, $i$번째 요청은 시각 $i$에 일어난다.

이미 캐시에 있고 아직 만료되지 않은 객체에 대한 요청은 비용 없이 처리된다. 요청한 객체가 캐시에 없거나, 캐시에 있더라도 만료되었다면 비용 $1$을 들여 캐시로 가져와야 한다. 아직 유효한 객체의 만료 시각만 갱신하는 것은 비용이 들지 않는다.

이미 가득 찬 캐시에 객체를 가져와야 할 때는, 교체 알고리즘이 현재 캐시에 있는 객체 중 하나를 골라 내보내 새 객체가 들어갈 자리를 만든다. 캐시는 처음에 비어 있다.

모든 요청은 미리 알려져 있다. 가능한 모든 교체 전략 중에서 총비용이 가장 작은 것을 찾아, 그 최소 비용을 출력하라.

첫째 줄에 캐시 용량을 나타내는 정수 $K$가 주어진다($6 \le K \le 100$).

둘째 줄에 요청의 개수를 나타내는 정수 $N$이 주어진다($6 \le N \le 1000$).

다음 $N$개의 줄에는 각각 두 정수 $P$와 $Q$가 주어진다. $P$는 요청한 객체이고, $Q$는 그 객체의 만료 시각(절대 시각, 그 시각 포함)이다.

요청은 주어진 순서대로 처리되며, 첫 요청은 시각 $1$에 일어나고 매 요청 후 절대 시각이 $1$씩 증가한다.

한 개의 정수를 출력한다. 최적의 교체 알고리즘이 수행하는 가져오기 횟수, 즉 최소 총비용이다.