Data Visualization: Top N and Other

A chart with thirty bars is unreadable. Keep the N biggest categories and fold the rest into Other, always shown last.

What to build

A program that prepares top-N data for a bar chart.

Requirements

  • Total the values per category. Print the N categories with the largest totals as NAME: TOTAL, largest first and alphabetically on ties, with totals in :g format.
  • If any categories are left over, print Other: TOTAL last, with the sum of their totals.

Input

Line 1: N. Line 2: n. Then n lines CATEGORY VALUE.

Output

Up to N + 1 lines.

Constraints

1 ≤ N ≤ 20; 1 ≤ n ≤ 1000; values are 0 or more; no category is called Other.

Example

Input:

2
7
Books 12.5
Toys 30
Books 7.5
Garden 45
Toys 10
Music 4
Games 3

Output:

Garden: 45
Toys: 40
Other: 27

Why it works

Aggregating first turns rows into one value per category, sorting puts the important bars first, and one Other bar keeps the long tail visible without letting it crowd the chart.

Examples

Example 1 · Input
2
7
Books 12.5
Toys 30
Books 7.5
Garden 45
Toys 10
Music 4
Games 3
Expected output
Garden: 45
Toys: 40
Other: 27
Example 2 · Input
5
2
a 1
b 2
Expected output
b: 2
a: 1

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Total the values per category first, then sort by total (largest first) and by name on ties.

Hint 2

Everything after the first N goes into one Other total.

Solution

Show one correct solution (try it yourself first)
top = int(input())
n = int(input())
totals = {}
for _ in range(n):
    c, v = input().split()
    totals[c] = totals.get(c, 0) + float(v)
ranked = sorted(totals.items(), key=lambda kv: (-kv[1], kv[0]))
for c, v in ranked[:top]:
    print(f"{c}: {v:g}")
if len(ranked) > top:
    print(f"Other: {sum(v for _, v in ranked[top:]):g}")

Lesson: Aggregating data for charts →