Problem D
Taking Inventory
Steve, Alex, and Kai have finally reunited after their initial trek for resources. Now, they decide to put all of their resources into chests for safekeeping. They’d like to know ahead of time how many chests they will need to store their combined set of items.
Given the names and amounts of each item across the three players’ inventories, determine how many inventory slots will be taken up by each item once they are optimally organized into chests.
Assume that items can be stored into stacks of up to 64. For example, if there are two slots containing wood, one with 32 items and one with 33, then wood will take up 2 inventory slots when organized (one stack of 64 and one stack of 1).
Input
The first line of input contains a single integer, $n$, the number of inventory slots that contain items. You are given that $1 \le n \le 10^5$.
The next $n$ lines each contain two values: a string $s$, the name of the item; and, an integer $c$, the quantity of that item present in the given inventory slot. The names will consist of at most 20 lowercase characters, while $1 \le c \le 10^4$. There may be duplicate names in the input, these items should be organized together.
Output
For each unique item name, $s_i$, print a line containing the string $s_i$ and an integer $m_i$, where $m_i$ is the number of inventory slots that item $s_i$ will take up once organized optimally. You may output the item names in any order.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 wood 32 wood 33 |
wood 2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 sapling 15 apple 1 sapling 30 |
apple 1 sapling 1 |