<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

127. Telephone directory

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


CIA has decided to create a special telephone directory for its agents. The first 2 pages of the directory contain the name of the directory and instructions for agents, telephone number records begin on the third page. Each record takes exactly one line and consists of 2 parts: the phone number and the location of the phone. The phone number is 4 digits long. Phone numbers cannot start with digits 0 and 8. Each page of the telephone directory can contain not more then K lines. Phone numbers should be sorted in increasing order. For the first phone number with a new first digit, the corresponding record should be on a new page of the phone directory. You are to write a program, that calculates the minimal number P pages in the directory. For this purpose, CIA gives you the list of numbers containing N records, but since the information is confidential, without the phones locations.


Input

The first line contains a natural number K (0 < K < 255) - the maximum number of lines that one page can contain. The second line contains a natural N (0 < N < 8000) - number of phone numbers supplied. Each of following N lines contains a number consisting of 4 digits - phone numbers in any order, and it is known, that numbers in this list cannot repeat.


Output

First line should contain a natural number P - the number of pages in the telephone directory.


Sample Input

5
10
1234
5678
1345
1456
1678
1111
5555
6789
6666
5000
Sample Output

5
Author	: Alex Y. Suslov, Victor G. Samoilov, Natalia L. Andreeva
Resource	: 5th Southern Subregional Contest. Saratov 2002
Date	: 2002-10-10

<|response|>
1. Abridged Problem Statement
CIA needs a telephone directory where:
- Pages 1–2 are reserved (no records).
- From page 3 onward, each page holds up to K phone-number records.
- Each phone number is a distinct 4-digit string not starting with 0 or 8.
- Records must be sorted, and whenever you start a phone number whose first digit differs from the previous record's first digit, you must begin a new page.
Given K and an unordered list of N valid phone numbers, compute the total pages P (including the 2 reserved pages).

2. Key Observations
- Sorting all numbers is not needed to count pages; you only need counts of each "first digit" group.
- There are at most 9 possible first digits (1–7,9).
- Each non-empty group of size s consumes ceil(s/K) pages.
- Finally, add 2 pages for the reserved front matter.

3. Full Solution Approach
a. Read K (max records per page) and N (number of phone numbers).
b. Maintain a map count[first_char] = 0.
c. For each of the N phone numbers, let d = first character of the number and increment count[d].
d. Let total_pages = 2 (for the reserved pages).
e. For each first-digit group with count > 0, add (count + K − 1) / K to total_pages (integer arithmetic for ceil(count/K)).
f. Output total_pages.

Time Complexity: O(N). Memory: O(1) extra.

4. C++ Implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

map<char, int> cnt;
int n, k;

void read() {
    cin >> k >> n;
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        cnt[s[0]]++;
    }
}

void solve() {
    // The first two pages are fixed (title + instructions). Numbers are
    // sorted, and every number sharing a first digit forms one contiguous
    // block that must begin on a fresh page, so the blocks never share a
    // page. cnt[d] is how many numbers start with digit d, and that block
    // needs ceil(cnt[d] / k) pages. The answer is 2 plus the sum of those
    // per-digit page counts.

    int ans = 2;
    for(auto [c, x]: cnt) {
        ans += (x + k - 1) / k;
    }

    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments
```python
import sys

def main():
    data = sys.stdin.read().split()
    # Parse K and N
    K = int(data[0])
    N = int(data[1])

    # Initialize counts for digits '1'..'9'
    counts = {str(d): 0 for d in range(1, 10)}

    # Count how many phone numbers start with each digit
    for i in range(N):
        phone = data[2 + i]
        first_digit = phone[0]
        counts[first_digit] += 1

    # We always have 2 reserved pages
    total_pages = 2

    # For each group, add the required pages
    for d in counts:
        s = counts[d]
        if s > 0:
            # ceil(s / K) = (s + K - 1) // K
            total_pages += (s + K - 1) // K

    # Print the total pages
    print(total_pages)

if __name__ == "__main__":
    main()
```
