1869. Bag

单点时限: 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 奖励。

创建: 16 年前.

修改: 6 年,7 月前.

最后提交: 2 年,1 月前.

来源: N/A

题目标签