Fairly Distribute Money With Limits

Problem: Fairly Distribute Money With Limits

You have a non-negative integer amount describing the total money available for distribution. Money is measured in indivisible integer units, such as cents.

There are also n employees, each described by:

• name: a distinct employee name
• limit: the greatest amount that employee may receive

Assign the money according to these requirements:

1. An employee's allocation must not exceed that employee's limit.
2. The allocation should be as balanced as possible: employees whose limits have not been reached should be brought to a common level whenever possible.
3. When an employee reaches their limit, any money still available must be divided fairly among the employees who remain below their limits.
4. If amount exceeds the combined limits, assign every employee their full limit and leave the surplus undistributed.
5. Because allocations are integers, distribute any leftover units from a final split in input order, giving the extra 1-unit amounts to the earliest employees first.

Report the amount ultimately assigned to every employee.

Input Format

amount n
name_1 limit_1
name_2 limit_2
...
name_n limit_n

Output Format

List the employees in the order they appeared in the input, together with their assigned amounts:

name_1 amount_received_1
name_2 amount_received_2
...
name_n amount_received_n

Constraints

• 0 <= amount <= 10^18
• 1 <= n <= 2 * 10^5
• 0 <= limit_i <= 10^18
• name_i is non-empty, unique, and contains no whitespace

Example 1

Input:

100 3
Alice 100
Bob 100
Charlie 100

Output:

Alice 34
Bob 33
Charlie 33

Explanation: Since 100 cannot be divided evenly among three employees, Alice receives the one-unit remainder because she is first in the input.

Example 2

Input:

150 3
Alice 40
Bob 100
Charlie 100

Output:

Alice 40
Bob 55
Charlie 55

Explanation: Alice is capped at 40, leaving 110 units to divide equally between Bob and Charlie.