**21 人解决**，50 人已尝试。

**22 份提交通过**，共有 111 份提交。

**6.3** EMB 奖励。

**单点时限: **10.0 sec

**内存限制: **256 MB

You have just begun working as a grocery bagger at the local ECNU food store. Your job is to place all of a customer’s items into bags, so they can be carried from the store. Your manager has instructed you to use as few bags as possible, to minimize the store’s overall cost. However, for the customer’s convenience, you are instructed that only items of the same type can be placed in the same bag. For instance, a produce item can be bagged with any other produce items, but not with dairy items.

There are many test cases!In each case the first line two interger n(1<=n<=100000),m(1<=m<=100000).n is indicating the maximum number of items that can be place in each bag,m indicats the number of the items name,then m lines of the item’s name followed.

Output an int indicating the minimum number of bags required to package the customer’s items.

Input

2 6 DAIRY DAIRY PRODUE PRODUE PRODUE MEAT 3 6 DAIRY DAIRY PRODUCE PRODUCE PRODUCE MEAT

Output

4 3 Hint: Case 1: Here, you have six items. You could put two items in each bag, but you would have to mix item types. The single meat item must get its own bag. The two dairy items fit in one bag. The three produce items will require two bags. Case 2: Similar to above, but now we have stronger bags. Note again, though, that if we were allowed to mix item types, we could get away with only 2 bags. But since item types cannot be mixed, we need 3 bags.

**21 人解决**，50 人已尝试。

**22 份提交通过**，共有 111 份提交。

**6.3** EMB 奖励。

**创建**: 14 年，11 月前.

**修改**: 5 年，7 月前.

**最后提交**: 1 年前.

**来源**: N/A

题目标签