# Tag Archives: SGU127

## SGU 127 解题报告

http://acm.sgu.ru/problem.php?contest=0&problem=127

## 127. Telephone directory

time limit per test: 0.50 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.

CIA（中央情报局）决定为它的代理商做一份特殊的电话号码簿。号码簿的前两页是一些使用说明和人名等一些乱七八糟的内容，从第三页开始记录电话号码。每一个电话记录都只有一行，它包括两个部分：电话号码和电话位置。电话号码长度是4，电话号码不能以0或8开头。电话号码簿的每一页不能超过K行。电话号码应该按照字典序排序。第一位的数字不同的电话号码不能出现在同一页。所以当电话号码第一位改变时，应该另起一页。你需要编写一个程序，计算最少需要的页数 P。为此，CIA已经给你了一份有N条电话记录的表格，但由于工作机密，CIA没有告诉你电话的位置，所以你不用考虑电话位置。

### 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.