swimming_pool_2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef vector<int> VE;
int n, m;
VE slots;

int convert(string s) {
    int H = 0, M = 0, S = 0;
    H = ((int)s[0] - 48)*10 + ((int)s[1] - 48);
    M = ((int)s[3] - 48)*10 + ((int)s[4] - 48);
    S = ((int)s[6] - 48)*10 + ((int)s[7] - 48);
    return H*3600 + M*60 + S;

}

void read() {
    string s;
    slots = VE(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> s;
        int t = convert(s);
        slots[i] = t;
    }
    sort(slots.begin(), slots.end());
}

bool enough(int x) {
    int k = 1, i = 1;
    int N = slots[0] + 60 + x;
    while (i < n) {
        while (slots[i] < N) {
            i++;
            if (i == n) return false;
        }
        k++;
        N = slots[i] + 60 + x;
        if (k == m) return true;
    }
    return false;
}

int bin_search(int a, int b) {
    if (b - a == 1) {
        if (enough(b)) return b;
        else return a;
    }
    else {
        int c = a + (b - a)/2;
        if (enough(c)) return bin_search(c, b);
        else return bin_search(a, c);
    }
}

int main() {
    cin >> m >> n;
    while (m != 0 or n != 0) {
        read();
        cout << bin_search(0, 86400 - 120) << endl;
        cin >> m >> n;
    }
}