Product Order Totals

Interview

Time limit1sMemory limit128 MB

Summary
Sum the order quantities for each distinct product name, then print each product with its total sorted by name length, then alphabetically.
Level

Medium4 of 10

Topics
Hash map, Sorting, String, Implementation
Solved
No attempts yet

Problem

A factory receives product-production orders from each of its sales offices. You want to aggregate the previous day's orders and compute the total production quantity for each product.

The first line of the input contains the number of order records nn. Each of the next nn lines contains a product name and an order quantity, separated by a space. A product name consists of at most 5 uppercase English letters. The same product may appear in more than one order record, and the records are given in no particular order.

Add up the order quantities for each distinct product, then output each product name together with its total, separated by a space. Print the products in the following order.

Ordering: sort by the length of the name in ascending order; when two names have the same length, sort them alphabetically, comparing character by character from the front and using the first position at which they differ.

Input

In the input data, the number of distinct products, each order quantity, and each product's total are all at most 10810^8.

Output

Print each product name and its total on its own line, following the ordering described above. Make sure the final line also ends with a newline character.

Examples2

  1. Example 1

    Input
    5
A 20
B 20
A 20
AB 10
Z 10
    Expected output
    A 40
B 20
Z 10
AB 10

  2. Example 2

    Input
    5
AAA 20
ABA 20
AAA 20
AAB 20
AAA 20
    Expected output
    AAA 60
AAB 20
ABA 20