Requests

Time limit1sMemory limit128 MB

Summary

Given a cache of capacity K and N timed requests with expiration times, compute the minimum number of fetches over all offline replacement strategies.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Intervals, Sorting
Solved: No attempts yet

Problem

You are given a collection of equal-size objects, a cache that can hold at most $K$ objects, and a sequence of $N$ requests. Each request asks for one object and carries an expiration time telling you until when (inclusive) that object stays valid.

Time starts at $1$ and advances by one unit after every request, so the $i$ -th request happens at time $i$ .

A request for an object that is already in the cache and has not yet expired is served at no cost. If the requested object is not in the cache, or it is in the cache but has expired, it must be fetched into the cache at a cost of one unit. Updating only the expiration time of an object that is still valid costs nothing.

Whenever an object must be fetched into a cache that is already full, a replacement algorithm chooses one currently cached object to evict so the new one fits. The cache starts empty.

All requests are known in advance. Among all replacement strategies, find the one with the least total cost, and output that minimum cost.

Input

The first line contains an integer $K$ , the cache capacity in number of objects ( $6 \le K \le 100$ ).

The second line contains an integer $N$ , the number of requests ( $6 \le N \le 1000$ ).

Each of the next $N$ lines contains two integers $P$ and $Q$ : $P$ is the requested object, and $Q$ is its expiration time (an absolute time, inclusive).

The requests are given in order; the first request occurs at time $1$ , and the absolute time advances by one unit after each request.

Output

Output a single integer: the minimum total cost, i.e. the number of fetches performed by an optimal replacement algorithm.

Examples3

Example 1
Input
```
3
6
1 2
2 4
2 4
3 5
3 9
2 9
```
Expected output
```
4
```

Example 2

Input

Expected output

Example 3
Input
```
6
6
1 1
1 2
1 3
1 4
1 5
1 6
```
Expected output
```
6
```