Bottom-K Customers by Revenue (with Nested Revenue Follow-up)

Problem: Aggregate Customer Revenue and Return the Bottom K Customers You are given a list of transactions. Each transaction contains: customer_id (string) and revenue (non-negative integer). Compute the total revenue per customer (sum of revenue) and output the K customers with the smallest total revenue (Bottom-K). Output requirements If the number of unique customers is less than K, output all customers. Sort the results by: total revenue ascending if tied, customer_id lexicographically ascending Output one customer per line: customer_id total_revenue Input format (stdin) Line 1: two integers N K Next N lines: customer_id revenue Constraints 1 <= N <= 2 * 10^5 1 <= K <= 10^5 0 <= revenue <= 10^9 customer_id is alphanumeric/underscore, length <= 64 Follow-up (discussion only, no implementation required) If revenue becomes nested revenue (e.g., each record contains a nested structure/array with multiple revenue entries to aggregate), how would you rewrite the approach? Only discuss: time complexity and space complexity optimizations for read-heavy vs write-heavy workloads (e.g., indexing/caching/pre-aggregation/incremental maintenance/approximation). Example Input 6 2 c1 10 c2 5 c1 3 c3 5 c2 1 c4 0 Output c4 0 c3 5