Lolek and Bolek are about to travel abroad by plane. The local airport has a special…
- User
Lolek and Bolek are about to travel abroad by plane. The local airport has a special "Choose Your Plane" offer. The offer's conditions are as follows:
- it is up to a passenger to choose a plane to fly on;
- if the chosen plane has x (x > 0) empty seats at the given moment, then the ticket for such a plane costs x zlotys (units of Polish currency).
The only ticket office of the airport already has a queue of n passengers in front of it. Lolek and Bolek have not stood in the queue yet, but they are already wondering what is the maximum and the minimum number of zlotys the airport administration can earn if all n passengers buy tickets according to the conditions of this offer?
The passengers buy tickets in turn, the first person in the queue goes first, then goes the second one, and so on up to n-th person. Input
The first line contains two integers n and m (1 ≤ n, m ≤ 1000) — the number of passengers in the queue and the number of planes in the airport, correspondingly. The next line contains m integers a1, a2, ..., am (1 ≤ ai ≤ 1000) — ai stands for the number of empty seats in the i-th plane before the ticket office starts selling tickets.
The numbers in the lines are separated by a space. It is guaranteed that there are at least n empty seats in total.
Output
Print two integers — the maximum and the minimum number of zlotys that the airport administration can earn, correspondingly.
Examples
Input
4 3 2 1 1
Output
5 5
Input
4 3 2 2 2
Output
7 6
Note
In the first test sample the number of passengers is equal to the number of empty seats, so regardless of the way the planes are chosen, the administration will earn the same sum.
In the second sample the sum is maximized if the 1-st person in the queue buys a ticket to the 1-st plane, the 2-nd person — to the 2-nd plane, the 3-rd person — to the 3-rd plane, the 4-th person — to the 1-st plane. The sum is minimized if the 1-st person in the queue buys a ticket to the 1-st plane, the 2-nd person — to the 1-st plane, the 3-rd person — to the 2-nd plane, the 4-th person — to the 2-nd plane.
Assistant
We need to solve the problem: Given n passengers sequentially buying tickets, and m planes each with initial empty seats (a_i). Each passenger can choose any plane that currently has x > 0 empty seats, and pays x zlotys (the number of empty seats at that moment). After purchase, that plane's empty seats decrease by 1. The process repeats. We need to compute the maximum possible total revenue and the minimum possible total revenue, assuming passengers choose planes optimally (from the airport's perspective? Actually, the problem asks: "what is the maximum and the minimum number of zlotys the airport administration can earn if all n passengers buy tickets according to the conditions of this offer?" I interpret as: The passengers can choose any plane (they are allowed to choose). So the airport administration's earnings depend on the choices passengers make. Since passengers might choose planes to either maximize or minimize the total? Actually, the problem asks for the maximum and minimum the airport can earn; presumably we consider that passengers might act in some way? Usually such problems: given that passengers can choose any plane, we need to compute the maximum and minimum possible total revenue that the airport can get, over all possible sequences of choices by passengers (each passenger can choose any plane with available seats). So we need to compute the extremal totals.
Thus, we need to simulate the process: Initially m planes with capacities (empty seats) a_i. For each of n steps, we select a plane with current empty seats >0, and add its current empty seat count to total, then decrement that count by 1. After n steps, we have total revenue. We want the max and min totals possible, assuming the selections are made arbitrarily (or perhaps optimally by passengers? but since they can choose, the airport might hope for max or min? Actually, it's a typical problem: "what is the maximum and minimum amount the administration can earn?" meaning the range of possible earnings depending on choices. So we must compute max and min.
Constraints: n, m up to 1000, a_i up to 1000. Total empty seats >= n. So we can simulate with greedy algorithms for max and min.
For maximum total: we want to maximize the sum of selected current seat counts. At each step, we would like to pick the plane with the highest current number of empty seats, because that gives the largest immediate payment. But is this always optimal? Let's consider: picking a plane reduces its future empty seats by 1, so it might reduce future payments. However, we want to maximize sum overall. Typically, to maximize revenue from selling seats where price equals remaining seats, we want to sell seats from the planes with larger capacities first, because each sale yields a higher price. This is analogous to: we have multiset of seat counts; each time we pick a value x, add x to sum, then replace x with x-1. To maximize total, we should always pick the largest available x. This can be proved by exchange argument: If at some step we pick a smaller value, and later pick a larger one, swapping them would increase total (or not decrease). Because picking a larger value earlier gives higher immediate revenue and also the later pick of the smaller value yields a smaller revenue, but the ordering matters? Let's check: Suppose we have two steps: pick x then y (with x <= y? Actually, we want to compare sequences). If we have two planes with current seats a > b. If we pick b first, then a, the contributions: b + (a). If we pick a first, then b, contributions: a + (b)?? Wait, after picking a first, a becomes a-1. Then picking b? But careful: When we pick a plane, we take its current seat count and then decrement it. So if we pick a first (value a), then the plane that had a becomes a-1. If later we pick the plane that originally had b (still b if not changed), the contributions: a + b. So same? However, if we pick b first, contributions: b + a (since a unchanged). So same total? That suggests order doesn't matter if we are picking from different planes? But what if we pick from the same plane multiple times? Then order matters. For maximum, we want to concentrate picks on the plane with highest current seats until it becomes equal to the next highest, etc. This is similar to: we have capacities; each time we pick a plane, we add its current number and reduce it by one. The total sum is sum over all picks of the current value. This is analogous to "selling tickets" problem where each seat sold yields price equal to remaining seats in that plane. The total revenue is the sum over all seats sold of the number of remaining seats in that plane at the moment of sale. If we think of each seat individually, each seat in a plane that originally had capacity a_i contributes to the revenue: when that seat is sold, the price equals the number of unsold seats in that plane at that time, including that seat. So if we label the seats of plane i as s_{i,1}, s_{i,2}, ..., s_{i, a_i} (in some order of sale). If we sell the k-th seat from plane i (i.e., that particular seat) when there are t unsold seats remaining in that plane, then it contributes t. The t is exactly the number of seats not yet sold in that plane, including that seat. So if we consider the order in which we sell seats from the same plane, the contributions are a_i, a_i-1, ..., 1 (if we sell all seats). So total revenue from plane i if we sell k_i seats from it (where 0 <= k_i <= a_i) is the sum of the largest k_i numbers from the decreasing sequence: a_i, a_i-1, ..., 1, i.e., sum_{j=0}^{k_i-1} (a_i - j) = k_i * a_i - (k_i-1)k_i/2 = k_i * (2a_i - k_i + 1) / 2. But careful: if we sell seats from a plane, the order of selling among planes does not affect the sum from each plane, provided we know how many seats we sell from each plane? Actually, the total revenue is the sum over all sold seats of the remaining capacity of its plane at the moment of sale. This depends on the interleaving of sales from different planes? Let's check: Suppose we have two planes A with capacity 3, B with capacity 2. We sell 2 seats from A and 1 from B. The contributions from A: if we sell two seats from A, the contributions from those seats depend on when we sell them relative to each other. But if we only sell two seats from A, the sum of contributions from those two seats will be 3 + 2 = 5 if the two sales of A happen without any B sales in between? Actually, suppose we sell seat A1, then later sell seat A2. At the moment of selling A1, the remaining seats in A is 3, so contribution 3. After selling A1, remaining seats in A becomes 2. Then later when we sell A2, contribution is 2. So sum = 5. If we interleave sales: sell A1 (3), then sell B1 (2) (since B had 2), then sell A2 (now A has 2 left? Actually after A1, A has 2 left; B after B1, B has 1 left; then selling A2 contributes 2). So still 3+2+2 = 7? Wait total sum = 3 (A1) + 2 (B1) + 2 (A2) = 7. But earlier we said total from A is 3+2=5, plus B's contribution 2 = 7. So sum from A is fixed as 3+2=5 regardless of interleaving? Actually if we had sold A1 and A2 without any interleaving, contributions: 3 and 2 -> 5. With interleaving, A1 still 3, A2 still 2 because after A1, A becomes 2, and if we sell B in between, A's remaining seats stay 2 until we sell A2, so A2 still 2. So indeed the contributions from a particular plane only depend on how many seats we have sold from it and the order of those sales relative to each other (they are sold in decreasing order of remaining seats) but not on interleaving with other planes: because the remaining seats count of plane i only changes when we sell from that plane; it is unaffected by sales from other planes. So the total contribution from plane i given we sell k_i seats from it is exactly the sum of the top k_i terms from the decreasing sequence: a_i, a_i-1, ..., 1. This is independent of when these sales occur relative to sales from other planes. Therefore, the total revenue is solely determined by the vector (k_1, ..., k_m) where sum k_i = n, 0 <= k_i <= a_i. The revenue = sum_{i=1}^{m} [k_i * a_i - (k_i-1)k_i/2] = sum_{i=1}^{m} [k_i * (a_i + (a_i - k_i + 1))/2? Wait: sum_{j=0}^{k_i-1} (a_i - j) = k_i * a_i - k_i(k_i-1)/2.
Thus, the problem reduces to: we have m planes with capacities a_i. We need to assign n "sales" to planes (each sale uses one seat) such that total revenue is maximized or minimized, with the revenue from plane i given k_i sales being f_i(k_i) = k_ia_i - k_i(k_i-1)/2. And constraints: 0 <= k_i <= a_i, sum k_i = n, and total seats sum a_i >= n.
We want max and min of sum f_i(k_i). Since f_i is concave? Let's examine: f_i(k) = -0.5 k^2 + (a_i + 0.5) k. Actually f_i(k) = a_ik - (k(k-1))/2 = a_ik - (k^2 - k)/2 = a_ik - k^2/2 + k/2 = -0.5 k^2 + (a_i + 0.5)k. This is a quadratic concave (coefficient -0.5 < 0). So the marginal benefit of selling an additional seat on plane i (i.e., the price of that seat) is: f_i(k) - f_i(k-1) = (a_i - (k-1)). Indeed, selling the k-th seat on plane i yields revenue equal to the number of empty seats before sale, which is a_i - (k-1). So marginal revenue is decreasing as k increases. This is intuitive: first seat yields a_i, next yields a_i-1, etc.
Thus, to maximize total revenue, we want to allocate sales to planes with the highest marginal revenue at each step. Since marginal revenues are decreasing, the greedy approach: at each step, pick the plane with the current highest marginal revenue (i.e., current empty seats). This corresponds to always picking the plane with the largest current a_i (where current a_i is original minus seats already sold). This greedy yields an optimal allocation because the problem is a separable concave resource allocation with integer constraints? Actually, maximizing sum of concave functions subject to sum of k_i = n is solved by a greedy that always increment the variable with the highest marginal gain, because concave functions have diminishing returns; we want to allocate to the highest marginal gains first. This is a standard result: For maximizing a separable concave function with integer variables and a sum constraint, the greedy of repeatedly adding one unit to the component with the highest incremental gain yields optimal solution. Since marginal gains are decreasing, this yields optimal.
Similarly, for minimizing total revenue, we want to allocate sales to planes with the lowest marginal revenue at each step. But careful: Since revenue is positive, we want as small total as possible, so we should sell seats on planes with the smallest current empty seat count, i.e., lowest marginal revenue. However, we have to be careful: if we pick a plane with small current empty seats, later its marginal revenue becomes even smaller (or negative? but it can't go below 1 because we only sell while seats >0). The greedy of always picking the smallest current empty seats might yield the minimum total. But is it always optimal? Let's consider the minimization problem. The objective is also concave? Actually f_i(k) is concave, but we want to minimize a sum of concave functions. Minimizing a concave function over a convex set is not convex; it's generally hard. But here the constraint set is discrete, but we have a specific structure: the functions f_i(k) are convex? Check second difference: f_i(k+1)-2f_i(k)+f_i(k-1) =? The marginal differences: d(k) = a_i - (k-1). Then d(k+1)-d(k) = -1. So the marginal differences decrease by 1 each step. So the sequence of marginal gains is linearly decreasing. This means the total f_i(k) as a function of k is concave (since second derivative negative if continuous). So we are minimizing a sum of concave functions subject to a sum constraint. This is generally a "knapsack" type where the objective is not convex; the greedy of picking smallest marginal may not be optimal because of the diminishing returns: allocating a seat to a plane reduces its future marginal revenue, possibly making it less attractive later, which might be beneficial for minimization (i.e., you want to keep marginal low). Actually, to minimize total, we want to keep the marginal values as low as possible across all steps. This is similar to "we want to sell seats in such a way that the price paid each time is as small as possible". Intuitively, we would want to sell from the planes with the smallest current empty seats, because that yields low immediate revenue and also reduces that plane's capacity further, keeping future revenues low. But could there be a scenario where picking a slightly larger current seat now leads to lower total later? Let's test small examples.
Example: n=2, m=2, a = [3, 1]. Total seats =4 >=2.
Possible allocations (k1, k2) with sum=2. Constraints: k1 <=3, k2 <=1. Options: (2,0): revenue = f1(2)=3+2=5; (1,1): revenue = f1(1)=3 + f2(1)=1 => total=4; (0,2) not possible because k2 max=1. So min=4, max=5.
Now greedy for min: at step1, choose plane with smallest current empty seats: both have 3 and 1, smallest is 1 (plane2). Pay 1, plane2 becomes 0. Next step, only plane1 has seats (3). Pay 3, total=4. That's min. If we picked plane1 first (pay 3), then plane2 (pay 1), total=4 as well? Actually that gives 3+1=4 also. So both give 4. So min=4.
Now consider a case where min greedy might be different? Let's try: n=2, m=2, a=[2,2]. Options: (2,0): revenue = 2+1=3; (0,2): 2+1=3; (1,1): 2+2=4? Wait careful: f1(1)=2, f2(1)=2 total=4. So min=3, max=4. Min greedy: smallest current seats initially both 2, tie. Pick any (say plane1) pay 2, plane1 becomes 1. Next step: smallest among {1,2} is 1 (plane1). Pay 1, total=3. So min=3 works. Alternative: pick plane1 first then plane2? Actually if pick plane1 first (2), then plane2 (2), total=4. That's max. So greedy for min (always pick smallest) gives min.
Now consider: n=3, m=2, a=[3,3]. Options: allocation (3,0): revenue = 3+2+1=6; (2,1): revenue from plane1: 3+2=5, plane2: 3=3? Wait f2(1)=3 total=8? Actually f1(2)=3+2=5, f2(1)=3 total=8; (1,2): 3 + (3+2)=8; (0,3): 3+2+1=6. So min=6, max=8? But check (2,1): total 5+3=8, (1,2): 3+5=8. So min=6, max=8. Min greedy: step1 smallest? both 3 tie -> pick say plane1 -> pay3, plane1->2. step2: values {2,3}, smallest=2 (plane1) -> pay2, plane1->1. step3: values {1,3}, smallest=1 (plane1) -> pay1, total=3+2+1=6. That's min. If we did different choices, could we get total <6? No, 6 is minimum. Good.
Now consider more complex: a = [1000, 1], n=2. Options: (2,0) -> 1000+999=1999; (1,1) -> 1000+1=1001; (0,2) not possible. So min=1001, max=1999. Min greedy: step1 smallest =1, pay1, plane2 becomes 0; step2 only plane1=1000, pay1000 total=1001. That's min. Good.
Consider a = [5,4,3], n=4. Let's enumerate possible allocations? We'll test min greedy. Step1: smallest current =3 (plane3) pay3, plane3->2. step2: values {5,4,2} smallest=2 (plane3) pay2, plane3->1. step3: values {5,4,1} smallest=1 (plane3) pay1, plane3->0. step4: values {5,4} smallest=4? Actually now planes: plane1=5, plane2=4, plane3=0. smallest=4 (plane2) pay4 total=3+2+1+4=10. Is there a lower total? Let's try allocation: sell 3 seats from plane3 (3,2,1) =6, and 1 seat from plane2 (4) =10 total. Alternative: sell 2 from plane3 (3+2=5) and 2 from plane2 (4+3? Actually if sell 2 from plane2, contributions: 4 then 3 =7, total=12; sell 2 from plane3 and 1 from plane2 and 1 from plane1: 5+? plane1 5, plane2 4, plane3 3+2? Actually careful: compute total for allocation (k1=1,k2=1,k3=2): f1(1)=5, f2(1)=4, f3(2)=3+2=5 total=14. (k1=1,k2=2,k3=1): 5+ (4+3)=12 +3? Wait f2(2)=4+3=7, f3(1)=3 total=5+7+3=15. (k1=2,k2=1,k3=1): f1(2)=5+4=9, f2(1)=4, f3(1)=3 total=16. (k1=0,k2=2,k3=2): f2(2)=4+3=7, f3(2)=3+2=5 total=12. (k1=0,k2=3,k3=1): f2(3)=4+3+2=9, f3(1)=3 total=12. (k1=0,k2=1,k3=3): f2(1)=4, f3(3)=3+2+1=6 total=10. (k1=1,k2=0,k3=3): 5+6=11. (k1=2,k2=0,k3=2):9+5=14. etc. Minimum seems to be 10 from (0,1,3) or (0,2,2) gives 12, (0,3,1)=12, (1,0,3)=11. So 10 is min. So greedy gave min 10.
Now consider a = [4,3,2] and n=4? Total seats=9. Let's test greedy min: step1 smallest=2 (plane3) pay2 -> plane3=1. step2 smallest=1 (plane3) pay1 -> plane3=0. step3 values {4,3} smallest=3 (plane2) pay3 -> plane2=2. step4 values {4,2} smallest=2 (plane2) pay2 -> total=2+1+3+2=8. Allocation (k1=0,k2=2,k3=2): f2(2)=3+2=5, f3(2)=2+1=3 total=8. Another allocation: (k1=1,k2=1,k3=2): f1=4, f2=3, f3=2+1=3 total=10. (k1=0,k2=1,k3=3): f2=3, f3=2+1+0? Wait f3(3)=2+1+0? but seat count can't go to 0? Actually if a_i=2, max k_i =2. So cannot. So min=8? Good.
Now try a more tricky one: a = [5,5,1], n=3. Greedy min: step1 smallest=1 (plane3) pay1 -> plane3=0. step2 values {5,5} smallest=5 (any) pay5 -> plane chosen becomes 4. step3 values {4,5} smallest=4 pay4 total=1+5+4=10. Is there lower total? Let's check all allocations. Constraints: plane3 max 1. So possible (k1,k2,k3) with sum=3, k3 <=1. Cases:
- k3=1: then k1+k2=2. Options: (2,0,1): f1(2)=5+4=9, f3(1)=1 total=10; (1,1,1): f1=5, f2=5, f3=1 total=11; (0,2,1): 5+4=9 +1=10. So min when k3=1 is 10.
- k3=0: then k1+k2=3. Options: (3,0): f1(3)=5+4+3=12; (0,3):12; (2,1): f1(2)=9, f2(1)=5 total=14; (1,2):5+9=14. So min 12. So overall min=10. So greedy gives min=10.
Thus far, greedy min (always pick smallest current) seems optimal. But is it always? Let's think about a potential counterexample where picking a slightly larger current now could lead to even smaller later picks, resulting in lower total. Since the objective is sum of marginal gains, it is equivalent to we have to choose a sequence of n numbers, each taken from some planes, with the condition that for each plane i, the sequence of numbers taken from it must be decreasing from a_i down to a_i - (k_i-1). The total sum is the sum of these numbers. This is similar to: we have m piles each with numbers from 1 to a_i (actually from a_i down to 1). We need to select n numbers (with the constraint that from pile i we cannot take a number unless we have taken all larger numbers from that pile? Actually, if we take a seat from a plane when it has x empty seats, that corresponds to taking the value x. After taking x, the next possible value from that plane is x-1 (if we take another seat). So indeed, if we take multiple seats from the same plane, the values must be strictly decreasing by 1 each time, starting from some initial value a_i (the first taken from that plane could be any value <= a_i? Actually, the first seat we take from a plane can only be taken when its current empty seats is exactly a_i (initial), so the value is a_i. The second must be a_i-1, etc. So we cannot skip numbers; we must take them in descending order. So the set of values we can take from a plane is a_i, a_i-1, ..., 1, and if we take k_i values, they must be the first k_i values: a_i, a_i-1, ..., a_i - k_i +1. So it's exactly the largest k_i numbers in that list. Therefore, the multiset of taken values is determined by the vector k_i, as earlier. So the problem is essentially: choose nonnegative integers k_i <= a_i summing to n, and compute sum over i of sum_{j=0}^{k_i-1} (a_i - j). Minimize or maximize this sum.
So it's a discrete resource allocation with separable concave objective. As we argued, maximizing a sum of concave functions subject to sum constraint is solved by greedy: allocate units to the component with highest marginal gain (i.e., highest current a_i). For minimization of sum of concave functions, it is the opposite? Usually, minimizing a concave function over a convex set is not nice; but here the domain is integer lattice points with bounds. However, because the functions are convex? Wait, check convexity: f_i(k) is not convex; it's concave. So sum is concave. Minimizing a concave function over a polytope (or integer points) is known to be achieved at extreme points of the feasible region (since concave functions have minima at extreme points). In our case, the feasible region is the set of integer vectors (k_i) satisfying 0 <= k_i <= a_i, sum = n. This is a "box" constraint plus a linear equality; it's a convex set (as integer lattice? but we treat as continuous for relaxation). For a concave function, its minimum over a convex compact set occurs at an extreme point of the set. The extreme points of the polyhedron {0 <= k_i <= a_i, sum k_i = n} (continuous relaxation) are those with as many variables at bounds (0 or a_i) as possible, because it's like a transportation polytope. Actually, the polyhedron is a product of intervals intersected with a hyperplane; its extreme points have at most one variable not at a bound. More precisely, the set {k_i in [0,a_i], sum k_i = n} is a convex polytope; its extreme points are of the form: one variable takes some value between its bounds, and all others are either 0 or a_i. This is analogous to the fact that the feasible region is a "knapsack" polytope. For concave minimization, the optimal solution of the continuous relaxation will be at an extreme point; then we might need to round. But here the variables are integer, so the integer feasible points are a subset. Usually, for separable concave minimization with linear constraints and box constraints, the optimal integer solution can be found by a "greedy" that picks the smallest marginal? I'm not entirely sure. However, we can think: we want to minimize sum of f_i(k_i) where f_i is concave increasing (since marginal positive). Since it's increasing, we would allocate as many as possible to planes with the smallest marginal gains? But because of concavity, the marginal gains decrease as k_i increases. So if we allocate a seat to a plane with currently small marginal (i.e., small a_i - (k_i-1)), that seat yields a small addition, but also reduces future marginals of that plane (making them even smaller). So continuing to allocate to the same plane yields diminishing returns, which is good for minimization because we keep the added values small. So concentrating sales on the plane with smallest initial capacity seems beneficial. But what about planes with medium capacities? Could splitting among many planes yield lower total than concentrating on the smallest? Let's test: Suppose we have two planes: a1=100, a2=100, n=100. If we concentrate on one plane (k1=100, k2=0), total = sum_{j=0}^{99} (100 - j) = 100+99+...+1 = 5050. If we split evenly (k1=50,k2=50), total = sum_{j=0}^{49} (100 - j) + sum_{j=0}^{49} (100 - j) = 2*(100+99+...+51) = 2*( (100+51)*50/2 ) = (151)*50 = 7550. So concentrating on one yields much lower total. That's because the later seats from the same plane cost less (down to 1), whereas splitting forces us to take higher values from the second plane as well. So indeed, for minimization, we want to fill up the smallest-capacity planes first? Actually, we want to minimize sum, so we want to use seats that cost as little as possible. The cheapest seats are those with small current empty seats. So we want to sell seats from planes that have the fewest empty seats. However, after selling a seat from a plane, its empty seats decrease by 1, making it even cheaper next time. So it's beneficial to keep selling from the same plane until it's exhausted, because that yields descending numbers: starting from a small number, then smaller, etc. So the strategy: at each step, pick the plane with the smallest current empty seats (if ties, any). This is the greedy for min that we've been using. It effectively concentrates sales on the plane with smallest initial capacity, then when that's exhausted, move to next smallest, etc. This yields an allocation where k_i are as "extreme" as possible: fill the smallest planes to capacity, then next, etc., until n seats sold. That seems plausible for minimization. Indeed, in the example a1=100, a2=100, min greedy: step1 both 100, smallest=100 tie -> pick one, it becomes 99; step2 smallest=99 (the same plane, if we continue picking the same plane? Actually greedy smallest: after picking plane1, values {99,100}; smallest is 99 (plane1), so we keep picking from the same plane. So we concentrate. So it gives k1=100, k2=0, total 5050, which is indeed lower than splitting. So greedy min works there.
Now consider a case where we have one plane with very large capacity and many small ones. The greedy min will first use the smallest planes, then move up. This seems intuitively minimal because it uses the smallest values first, then somewhat larger values, but avoids using very large values until necessary. Could there be a scenario where it's better to not completely exhaust a small plane, because using a slightly larger plane could yield even smaller future values? For instance, if a small plane has capacity 2, we take 1 seat costing 2, then if we take another seat from it, it costs 1. That yields total 3 for two seats. If we instead take one seat from a plane with capacity 3 costing 3, and then the next seat from the small plane costing 2 (since it still has 2), total = 5 vs 3? Obviously worse. But what about taking one seat from small (2), then the second from another small (2) gives 2+2=4, worse than 2+1=3. So exhausting is better. So it's always beneficial to continue on the same plane until it's empty, because the next seat from that plane is cheaper than any other seat currently available (since after taking some seats, its current seats become low). But careful: after taking a seat from a plane with initial small a, its current becomes a-1, which might still be not the smallest among all? If there is another plane with even smaller current? For example, plane A: capacity 3, currently 2 after one sale; plane B: capacity 2, hasn't been touched, so its current is 2 as well (or 2? Actually capacity 2 means current=2 initially). So after taking one from A (pay3) A becomes 2; now both A and B have 2. Which one to pick next? If we pick from A again, we pay 2 then A becomes 1; if we pick from B, we pay 2 then B becomes 1. The total after two picks: if we pick A twice: 3+2=5; if we pick A then B: 3+2=5; same. So not a difference. But consider: A=3, B=1 (capacity 1). Initially: smallest is B=1. Greedy min picks B: pay1, B exhausted. Then picks A: pay3, total=4. Alternative: pick A first: pay3, A becomes2; then pick B: pay1, total=4. same. So no difference.
But consider more complex: three planes: capacities [3,2,2], n=3. Greedy min: step1 smallest among {3,2,2} =2 (choose one of the 2's). Suppose pick plane2 (cap2). Pay2, plane2 becomes1. step2: values {3,1,2} smallest=1 (plane2). Pay1, plane2 becomes0. step3: values {3,0,2} smallest=2 (plane3). Pay2 total=2+1+2=5. Allocation: k2=2, k3=1, k1=0 => f2(2)=2+1=3, f3(1)=2 total=5. Another allocation: k1=1,k2=1,k3=1: f1=3, f2=2, f3=2 total=7. Another: k1=0,k2=2,k3=1 gives 5; k1=0,k2=1,k3=2 gives f2=2, f3=2+1=3 total=5; k1=1,k2=2,k3=0:3+3=6; k1=1,k2=0,k3=2:3+3=6; k1=2,k2=1,k3=0:3+2? Actually f1(2)=3+2=5, f2=2 total=7? Wait 5+2=7. So min=5. Good.
Now consider [4,3,3], n=3. Greedy min: smallest among {4,3,3} =3, pick one, say plane2. Pay3, plane2->2. Step2: values {4,2,3} smallest=2 (plane2) pay2, plane2->1. Step3: values {4,1,3} smallest=1 (plane2) pay1, total=3+2+1=6. Allocation: k2=3, others 0 => f2(3)=3+2+1=6. Another allocation: pick plane3 similarly. If we try to split: e.g., one seat from each: 4+3+3=10. Or two from one and one from another: e.g., k2=2 (3+2=5) and k3=1 (3) =8. So min=6. So greedy works.
Now consider [5,4,3,2], n=5. Greedy min: always pick smallest. Sequence: start: 2 (pay2) -> becomes1; then 1 (pay1) -> becomes0; then values {5,4,3} smallest=3 (pay3) -> becomes2; then {5,4,2} smallest=2 (pay2) -> becomes1; then {5,4,1} smallest=1 (pay1) -> total =2+1+3+2+1=9. Allocation: k4=2 (plane with cap2 used fully: 2+1=3), k3=2? Actually we used plane3? Let's track: after first two picks, plane4 (cap2) used twice? Actually plane with initial 2: we used it twice: 2 then 1 -> exhausted. Then next we used plane3 (cap3): 3 then 2 -> after two picks it becomes 1? We did: pick from plane3 (cap3) pay3 -> plane3 becomes2; then next smallest among {5,4,2} is 2 (plane3) pay2 -> plane3 becomes1; then final pick smallest=1 (plane3) pay1. So plane3 used three times? Actually we did 3 picks from plane3? Let's recount: after plane4 exhausted, we had 3 picks remaining. Step3: pick from plane3 (value3) -> plane3 becomes2. Step4: pick from plane3 (value2) -> plane3 becomes1. Step5: pick from plane3 (value1) -> plane3 becomes0. So plane3 used 3 times. So k4=2, k3=3, k1=0,k2=0 total f4(2)=2+1=3, f3(3)=3+2+1=6 total=9. Alternative allocation: use plane4 fully (2+1=3), plane2 fully? Plane2 cap4: but we need total 5, so could do k4=2, k2=3 => f2(3)=4+3+2=9, f4=3 total=12. Or k4=2, k1=3 => f1(3)=5+4+3=12, total=15. Or k3=3, k2=2 => f3=6, f2=4+3=7 total=13. Or k1=5 => f1=5+4+3+2+1=15. So min seems 9. Greedy gives 9.
What about [100,99,98,...] something? It seems plausible.
But we need a rigorous justification: The minimization problem is essentially: choose n numbers from the multiset of all values a_i, a_i-1, ..., 1 for each plane, with the condition that if we take a value x from a plane, we must also take all larger values from that plane? Actually, we must take a contiguous block from the top: the k_i largest values. So it's like we have m sorted decreasing sequences. We need to pick n numbers in total, each time picking a number from some sequence, and when we pick a number from a sequence, we must have already picked all numbers above it? Actually, in the process of selling seats, we can pick any sequence order, but the set of values taken from each plane is exactly the top k_i numbers. So in terms of chosen multiset, it's equivalent to selecting k_i numbers from plane i which are the numbers a_i, a_i-1, ..., a_i - k_i +1. So the multiset of chosen values is exactly the union of these intervals.
Thus, we can think of the problem as: we have m piles, each pile i has numbers: a_i, a_i-1, ..., 1. We need to select n numbers from these piles, but we can only take numbers from the top of each pile (i.e., we have to take a prefix of each pile). This is equivalent to we choose a cutoff for each pile: we take the first k_i numbers. The total sum is sum of the selected numbers. To minimize sum, we want to pick the smallest numbers overall, but we are constrained to take prefixes: if we want to take a small number from a pile, we must also take all larger numbers in that pile. This trade-off is reminiscent of the classic "minimum sum of k elements with the constraint that you can only take elements from certain sets with prefix condition" which often is solved by a greedy algorithm that repeatedly picks the smallest available element from the piles, but that would correspond to picking numbers from the bottom of piles? But we cannot pick the bottom without also picking the top. Wait, careful: In the actual process, you can't directly pick a small number from a pile without having first picked all larger numbers from that pile because the plane's empty seats decrease only after each sale. To get to the value x, you must have sold all seats that correspond to values > x. So indeed, to take the value 1 from a plane of capacity a, you must have taken all values a, a-1, ..., 2 before. So the numbers from a plane are taken in decreasing order. So if we want to include a low value, we must include all higher values from that plane. So the selection is prefix from the top. So the selection of numbers is essentially: we choose for each plane how many seats to sell (k_i), and then we sum the largest k_i numbers from that plane. So our earlier formulation is correct.
Now, to minimize sum_{i} f_i(k_i) with sum k_i = n, k_i in [0, a_i]. Since f_i is increasing and concave, one might think that to minimize sum, we want to make the k_i as unbalanced as possible, i.e., concentrate all sales on the smallest a_i? Actually, f_i(k) grows as roughly a_i k - k^2/2. For fixed sum k, the sum of concave functions is minimized when the allocation is as unequal as possible? Let's analyze: For two variables, consider f1(k) + f2(n-k) with 0 <= k <= min(a1, n) and n-k <= a2. The function g(k) = f1(k) + f2(n-k). Since f1 and f2 are concave, g(k) is concave as sum of concave functions? Actually, f2(n-k) is a function of k; but f2(n-k) as a function of k is convex? Let's compute: let h(k) = f2(n-k). f2 is concave, but composition with a linear decreasing argument: if φ(x) = f2(x) concave, then ψ(k)=φ(n-k) is also concave? Because φ is concave => φ(λx+(1-λ)y) >= λφ(x)+(1-λ)φ(y). Then ψ(λk1+(1-λ)k2)=φ(n-(λk1+(1-λ)k2))= φ(λ(n-k1)+(1-λ)(n-k2)) >= λ φ(n-k1)+(1-λ) φ(n-k2)= λ ψ(k1)+(1-λ) ψ(k2). So ψ is also concave. So sum of two concave functions is concave. So g(k) is concave. Minimizing a concave function over an interval: the minimum occurs at an endpoint (since concave functions have maxima in interior, minima at boundaries). So for two planes, the minimum total is achieved at either k=0 or k=n (subject to bounds). That is, either sell all seats from one plane (if possible) or the other, whichever gives lower total. This suggests that to minimize sum across many planes, we should concentrate sales as much as possible onto a single plane (the one that yields the smallest total for given n, considering its capacity). But we also have capacity constraints: if a_i < n, we cannot put all n in that plane; we must use multiple planes. Then the optimal solution would be to fill the smallest planes first (since they have lower values) and then move to larger ones only when necessary. This matches the greedy that always picks the plane with the smallest current seat count (which effectively concentrates on the smallest capacity planes, filling them completely before moving to larger ones).
More formally, we can think of the minimization as a kind of "water-filling" from the bottom: we want to choose k_i to minimize sum f_i(k_i) subject to sum k_i = n. Since f_i(k) is increasing and strictly concave, the marginal cost (or rather marginal revenue) is decreasing. To minimize total, we want to allocate seats to planes with the smallest marginal values at each step, i.e., we want to increase k_i on those i where the next marginal (a_i - k_i) is smallest. This is exactly the greedy algorithm: repeatedly pick the plane with smallest current (a_i - k_i) (which is the next marginal if we were to add one more seat). Starting with k_i=0, current empty seats = a_i. The greedy picks the smallest a_i, adds 1 to that plane, updates its current to a_i-1 (which might still be smallest), and continues. This yields an allocation where we increment the k_i with smallest (a_i - k_i) at each step. This greedy algorithm is known to give optimal solution for minimizing sum of increasing convex functions? Wait, the marginal of f_i at k_i is a_i - (k_i -1). That's decreasing. So the marginal is decreasing. If we think in terms of cost, we want to assign units to items with smallest marginal gain to keep total low. Since marginal gains are decreasing, the greedy that always picks the smallest current marginal (i.e., the smallest a_i - k_i) is optimal. This can be proved by an exchange argument: Suppose we have an optimal allocation where at some point we have a plane i with current empty seats x and plane j with y, with x < y, but we have assigned more seats to j and fewer to i? Actually, we need to argue that in an optimal min allocation, the k_i are such that the final marginal values (a_i - k_i) are as "balanced" as possible but reversed? Let's attempt exchange argument: Let two planes i and j with initial capacities a_i <= a_j. Suppose in an optimal allocation we have k_i < a_i (i not fully used) and k_j > 0 (some used on j). Consider moving one seat from j to i (i.e., decrease k_j by 1, increase k_i by 1). The change in total revenue: new total = old total - [f_j(k_j) - f_j(k_j-1)] + [f_i(k_i+1) - f_i(k_i)] = old total - (a_j - (k_j-1)) + (a_i - k_i). Since k_i < a_i and k_j >0. Now note that a_i - k_i >=? Since a_i <= a_j and we have some pattern? We need to show that moving a seat from the plane with larger current marginal to the one with smaller current marginal reduces total? Actually, we want to show that if we have a plane with smaller current marginal (i.e., smaller a_i - k_i) than another plane's current marginal, then we can shift a seat from the plane with larger marginal to the one with smaller marginal to decrease total? Wait, we want to minimize total. If we move a seat from j to i, the change Δ = (a_i - k_i) - (a_j - (k_j-1)). If (a_i - k_i) < (a_j - (k_j-1)), then Δ < 0, meaning total decreases. So if there exists two planes where the marginal for the next seat on i is smaller than the marginal for the last seat on j (i.e., the current empty seats of i (a_i - k_i) is smaller than the current empty seats of j after removing one seat (a_j - (k_j-1))? But we can also think of the state: suppose after allocation, the final "remaining seats" are r_i = a_i - k_i. The marginal for the last seat sold on i is r_i + 1? Actually careful: if we sold k_i seats from plane i, the last seat sold contributed a_i - (k_i-1) = r_i + 1. And the next seat (if we were to add one) would contribute r_i. In an optimal allocation, we want the sequence of marginal contributions to be as small as possible overall. An exchange argument: Consider two planes i and j such that the marginal for an additional seat on i (which is r_i) is less than the marginal for the last seat sold on j (which is r_j+1). If r_i < r_j+1, then we could move one seat from j to i (i.e., sell one less from j and one more from i) and the total would change by (r_i) - (r_j+1) < 0, so total decreases. Therefore, in an optimal (minimal) allocation, we must have for any two planes i and j with k_i < a_i and k_j > 0, that r_i >= r_j+1. In other words, the values r_i (remaining seats after allocation) should be such that the smallest r_i among planes that are not full is at least the largest (r_j+1) among planes that have positive sales? Actually, we can rearrange: For any i, j, we must have (a_i - k_i) >= (a_j - (k_j - 1))? That is, the next marginal on any plane that still has capacity (i.e., if we were to add a seat) must be at least the last marginal on any plane that we have used. In other words, the sequence of marginal values from sold seats (which are exactly the numbers a_i, a_i-1,..., a_i - k_i +1 for each i) should be as small as possible, and they should be the n smallest possible values from the multiset of all values under the prefix constraints. Actually, there is a known result: The minimum total is achieved by taking the n smallest numbers from the combined set of sequences, but with the condition that if you take a number from a sequence you must take all larger numbers from that sequence. That's a classic problem: we have m sorted lists (nonincreasing), we need to pick n numbers total, and if we pick the t-th number in a list, we must also pick all numbers before it. The goal is to minimize sum. The greedy algorithm that always picks the smallest available number (i.e., the smallest among the current heads of the lists) does NOT work because of the prefix constraint; you cannot pick a small number without picking the larger ones first. But in our setting, we are not picking numbers arbitrarily; we are forced to pick from top down. So the selection is exactly prefixes. So we are deciding how many to take from each list. The problem of minimizing the sum of selected elements under a total count constraint when each list contributes its top elements is known to be solved by a greedy algorithm that always picks the list with the smallest current head (i.e., the next element if we were to take one more from that list) to add to the selection. This is analogous to the following: We start with no seats taken. At each step, we consider for each plane the value we would pay if we sold one more seat from it (its current empty seat count). To minimize total, we want to pick the smallest such value. This is exactly the greedy we described. And this greedy yields an optimal allocation because it's equivalent to repeatedly taking the smallest possible next element given that we have already taken some prefixes. Since the marginal costs are decreasing, this greedy yields the set of n smallest possible marginal values that can be achieved respecting the prefix constraints. This is essentially a matroid? The constraints that we can only take prefixes can be formulated as a matroid? Possibly a knapsack? But I'm convinced that the greedy works for minimization as well based on exchange arguments.
Nevertheless, we can also compute min and max using priority queues efficiently: For max, use a max-heap of current empty seats. For min, use a min-heap. At each of n steps, pop top, add value to total, push value-1 if >0. That simulates the process. Since n,m <= 1000, we could even simulate by sorting each time O(nm) but better O(n log m) with heap. But n,m <= 1000, so even O(nm) (1000*1000=1e6) is fine. But using heap is simple.
But we must verify that the greedy for min indeed yields the minimum total. I'll try to find a counterexample. Let's do a systematic search for small parameters to see if greedy min ever fails. Since constraints are small, we could brute-force for all possible sequences? But number of sequences can be huge. However, we can brute-force the allocation vectors (k_i) for small m, n, a_i <= small values. Let's attempt to think of potential failure.
Consider a scenario with three planes: capacities [5,4,4], n=4. Greedy min: start: smallest among {5,4,4} = 4 (choose one of the 4s). Suppose pick plane2 (cap4). Value 4, then becomes 3. Step2: {5,3,4} smallest=3 (plane2) value 3, becomes2. Step3: {5,2,4} smallest=2 (plane2) value2, becomes1. Step4: {5,1,4} smallest=1 (plane2) value1, total=4+3+2+1=10. So k2=4, k1=0, k3=0, total=10. Alternative allocation: k3=4? same 10. Alternative: k1=1,k2=3: f1(1)=5, f2(3)=4+3+2=9 total=14. k1=2,k2=2: 5+4=9 + (4+3)=7? Actually f1(2)=5+4=9, f2(2)=4+3=7 total=16. k1=1,k2=1,k3=2: 5+4+ (4+3? f3(2)=4+3=7) total=5+4+7=16. So min=10. Good.
Now consider [5,5,2], n=4. Greedy min: smallest=2 (plane3) value2 -> becomes1; step2: smallest=1 (plane3) value1 -> becomes0; step3: smallest among {5,5} =5 (say plane1) value5 -> becomes4; step4: smallest among {4,5}=4 (plane1) value4 -> total=2+1+5+4=12. Allocation: k3=2, k1=2, k2=0 => f3(2)=2+1=3, f1(2)=5+4=9 total=12. Alternative allocations: k1=4: total =5+4+3+2=14; k1=3,k3=1: f1(3)=5+4+3=12, f3(1)=2 total=14; k2=3,k3=1: same 14; k1=2,k2=2: 9+9=18; k1=2,k2=1,k3=1:9+5+2=16; So min=12. Good.
Now consider [4,3,3,3], n=5. Greedy min: smallest initially among {4,3,3,3} =3 (choose one). Let's simulate: pick from a 3 (say plane2) -> value3, becomes2. Next smallest among {4,2,3,3}=2 (plane2) -> value2, becomes1. Next smallest among {4,1,3,3}=1 (plane2) -> value1, becomes0. Now used 3 from plane2. Remaining seats to sell: 2. Current: {4,0,3,3}. Smallest=3 (pick plane3) -> value3, becomes2. Then smallest among {4,0,2,3}=2 (plane3) -> value2, total = 3+2+1+3+2=11. Allocation: k2=3, k3=2, others 0 => f2(3)=3+2+1=6, f3(2)=3+2=5 total=11. Alternative allocations: Use all from one 3-plane: k2=3, k3=2 as above. Could we do k1=1, k2=3, k3=1? f1=4, f2=6, f3=3 total=13. k1=2,k2=3: f1(2)=4+3=7, f2=6 total=13. k1=1,k2=2,k3=2:4+ (3+2=5) + (3+2=5)=14. k1=0,k2=3,k3=3? But sum=6 >5, but we need 5, so k2=3,k3=2 or k2=2,k3=3. Both give 6+5=11. So min=11. Good.
Now consider [5,4,1,1], n=4. Greedy min: smallest=1 (plane3) -> value1, becomes0; step2: smallest among {5,4,0,1}=1 (plane4) -> value1, becomes0; step3: smallest among {5,4}=4 (say plane2) -> value4, becomes3; step4: smallest among {5,3}=3 (plane2) -> value3, total=1+1+4+3=9. Allocation: k3=1, k4=1, k2=2, k1=0 => f2(2)=4+3=7, plus 1+1=9. Alternative allocations: Could we do k1=1, k3=1, k4=1, k2=1: 5+1+1+4=11; k2=3,k3=1: f2(3)=4+3+2=9, plus1=10; k1=2,k3=1,k4=1: f1(2)=5+4=9 +2=11? Actually plus 1+1=11. k1=3,k3=1: f1(3)=5+4+3=12+1=13. So min=9. Good.
Now consider a scenario where there is a plane with capacity 2 and another with capacity 100, and n=3. a=[100,2]. Greedy min: pick smallest: 2 -> becomes1; then smallest: 1 -> becomes0; then pick 100 -> total=2+1+100=103. Allocation: k2=2, k1=1 => f2=2+1=3, f1=100 total=103. Alternative allocation: k1=3? f1=100+99+98=297. k1=2,k2=1: f1=100+99=199, f2=2 total=201. k1=1,k2=2:100+3=103 again. So min=103.
Now consider [100,50,50], n=100. Greedy min: would pick from the smallest? Initially smallest=50. It would keep picking from one 50 until it's exhausted? Actually step1: smallest=50 (pick one). It becomes49. Next smallest=49 (same plane) vs other 50? The other 50 still 50, so 49 is smaller, so continue on same plane. So it will exhaust that plane completely (50 seats) costing sum 50+49+...+1 = 1275. Then it has 50 more seats to sell from the other 50 plane? Actually after exhausting first 50, remaining seats: first plane? Wait we had three: 100,50,50. After using one 50 fully (k=50), we have 100,50 left, with 50 seats left to sell. Greedy then will pick the smallest among {100,50} which is 50, and will exhaust that 50, costing another 1275. So total = 1275+1275 = 2550. Then we have sold 100 seats. That's total 2550. Alternative allocation: Could we do k=100 on the 100 plane? That sum = 100+99+...+1 = 5050. So higher. What about k=50 on 100 and k=50 on one 50? That would be: from 100 plane: sum of top 50 = 100+99+...+51 = (100+51)50/2 = 15125 = 3775? Actually compute: sum_{j=0}^{49} (100-j) = 100+99+...+51 = (100+51)50/2 = 15125 = 3775. From 50 plane: sum of top 50 = 1275. Total = 5050. That's higher. What about k=100 from the 100 plane? 5050. So greedy min seems lower. But could we do something like k=100 from one of the 50? Not possible because max 50. So min seems 2550.
Now consider [100, 60, 40], n=100. Greedy min: always pick smallest. Start with 40, exhaust it (40 seats): sum_40 = 40+39+...+1 = 820. Then remaining seats to sell: 60. Now we have 100 and 60. Pick smallest 60? Actually between 100 and 60, smallest is 60, so we exhaust 60? But we need 60 seats, we have 60 left to sell. So we take all 60 from the 60 plane: sum_60 = 60+59+...+1 = 1830. Total = 820+1830=2650. Alternative allocation: Could we take some from 100 plane to reduce total? Suppose we take k1 from 100, k2=40 (full), k3=60 (full) sum k=140, but we only need 100, so we can't take full all. So we need to allocate 100 seats among capacities 100,60,40. To minimize, we probably want to use the smallest capacities first. So using full 40 and full 60 uses 100 exactly, as greedy does. So total = sum_40 + sum_60 = 820+1830=2650. What about using 40 fully and then 60 from 100? That would be 40 fully (820) + from 100: take 60 seats: sum of top 60 of 100 = 100+99+...+41 = (100+41)60/2 = 14130 = 4230. Total = 5050, higher. Using 60 fully and 40 from 100: 1830 + sum of top 40 of 100 = 100+...+61 = (100+61)40/2 = 16120 = 3220, total = 5050 again. Using only 100 plane: 5050. So indeed greedy yields minimum.
Now consider a scenario where capacities are not monotonic? The greedy min (always pick smallest current) seems to produce an allocation where we fill the smallest planes first. This is analogous to the "minimum sum of k elements under prefix constraints" and known to be optimal. I'll attempt to prove: For each plane i, define the sequence of costs: c_i(1)=a_i, c_i(2)=a_i-1,..., c_i(a_i)=1. We need to select exactly n costs, with the property that for each i, we select a prefix of its sequence (i.e., if we select c_i(t) then we must select c_i(1...t)). The total sum is sum of selected costs. To minimize, we want to select the n smallest possible costs subject to the prefix condition. This is equivalent to selecting the n smallest elements from the union of these sequences, but with the constraint that if we pick an element at position t, we must also pick all earlier positions (which are larger). So it's not simply picking the n smallest numbers because those might come from different sequences and we would need to include larger ones as well. However, the greedy algorithm that always picks the smallest available next cost (i.e., among the next cost of each sequence, which is c_i(k_i+1) where k_i currently selected) yields exactly the set of n smallest possible costs that can be selected respecting the prefix condition. This is because at any step, the smallest available next cost must be included in any optimal solution that still needs to select that many items? I think it's a matroid or a greedy algorithm on a polymatroid? There is known result: For the problem of minimizing sum of selected elements with prefix constraints, the greedy algorithm that picks the smallest available next element is optimal. This can be proved by exchange: Suppose we have an optimal selection that does not include the smallest next element at some step. Then we can swap something to include it without increasing sum. More formally, consider the set of selected positions: For each plane i, we select the first k_i positions. The multiset of selected values is S = { a_i - j | 0 <= j < k_i }. Let's sort these values descending? Actually we care about the sum. Suppose we have an optimal selection (k_i) and we compare it to the greedy selection (k_i^g). The greedy algorithm can be seen as at each step adding one to the i with smallest current (a_i - k_i). This is equivalent to a "water-filling" from the bottom: it tries to make the final remaining seats (a_i - k_i) as balanced as possible but with the smallest ones used up? Actually, the greedy for min results in the final remaining seats (a_i - k_i) being as large as possible for the planes that are not fully used? Let's think: After allocation, the values r_i = a_i - k_i are the remaining empty seats. Since we sold n seats, sum r_i = total_empty - n. The greedy min tends to make r_i as unequal as possible? Actually, starting from smallest a_i, we reduce them to zero, then move to next smallest, etc. So the final r_i are: some planes have r_i = 0 (the ones fully used), and the last plane maybe partially used, and larger planes untouched? Actually, if total_empty - n is some value, the greedy min will keep r_i as small as possible for the small planes, i.e., drive them to zero, and then the remaining seats are concentrated on the largest plane(s). So the r_i are extreme: many zeros, and then the rest on the largest. That seems like the opposite of balanced. But we are minimizing sum of sold seats, which is total original empty seats minus sum of remaining seats? Actually total revenue = sum of sold seat values. But note that sum of original empty seats = S = sum a_i. After selling n seats, the remaining empty seats are R = S - n. However, the revenue is not directly S minus something? Let's compute: revenue = sum over sold seats of current empty seats. Another relationship: total revenue = sum over all planes of (sum_{j=0}^{k_i-1} (a_i - j)). There is known identity: sum_{j=0}^{k_i-1} (a_i - j) = k_i * a_i - k_i(k_i-1)/2 = (a_i + (a_i - k_i + 1)) * k_i / 2. Not directly S - R. But we can also think: The sum of all numbers from 1 to a_i is a_i(a_i+1)/2. If we sell k_i seats, we are taking the top k_i numbers. The remaining numbers (from 1 to a_i - k_i) sum to (a_i - k_i)(a_i - k_i +1)/2. So revenue = total sum of all numbers (over all planes) - sum of numbers not sold. The total sum of all numbers (i.e., sum of 1..a_i over i) = sum_i a_i(a_i+1)/2. The numbers not sold are exactly the bottom (a_i - k_i) numbers of each plane, which sum to sum_i (a_i - k_i)(a_i - k_i +1)/2. So revenue = total_all - sum_i (a_i - k_i)(a_i - k_i +1)/2. Since total_all is constant, minimizing revenue is equivalent to maximizing sum_i (a_i - k_i)(a_i - k_i +1)/2. But (a_i - k_i) are the remaining seats. So maximizing sum of (r_i)(r_i+1)/2. Since this is a convex function in r_i? Let's check: f(r) = r(r+1)/2 = (r^2 + r)/2, which is convex (quadratic with positive coefficient). So we need to maximize a convex function over integers r_i >= 0, with sum r_i = S - n, and r_i <= a_i (since k_i >=0 => r_i <= a_i). Maximizing a convex function over a convex set typically pushes the solution to extremes: the maximum of a convex function over a convex polytope is attained at an extreme point. So to maximize convex sum, we want r_i as extreme as possible, i.e., as many r_i at bounds (0 or a_i) as possible. Since sum r_i is fixed, to maximize a convex sum we want the distribution to be as unequal as possible: put as much as possible into one variable, and others as small as possible. That is, we want some r_i to be as large as possible (up to a_i) and others as small as possible (0). But careful: constraints: r_i <= a_i, and sum r_i = R. To maximize sum of convex functions, we want to concentrate R into as few variables as possible, ideally one variable taking min(R, a_i) and the rest 0. However, we also have upper bounds a_i; if the largest a_i is less than R, we might need to split. This corresponds to the greedy min algorithm: we minimize revenue <=> maximize sum of r_i(r_i+1)/2. The greedy min algorithm leads to r_i that are as "unbalanced" as possible: we first reduce the smallest a_i to 0, i.e., set r_i = 0 for small planes, then the remaining R is allocated to the largest plane(s). That yields an extreme distribution: many zeros, and the rest on the largest plane(s). This seems to maximize the convex sum. So indeed, the greedy min yields optimal.
We can formally prove: Since maximizing a separable convex function with a sum constraint and bounds is solved by a greedy that allocates as much as possible to the variable with the largest marginal gain of the objective. But our objective in terms of r_i is convex, so its marginal gains are increasing. The marginal gain of increasing r_i by 1 (i.e., not selling a seat, keeping one more empty seat) is: Δ_i(r_i) = ( (r_i+1)(r_i+2)/2 - r_i(r_i+1)/2 ) = r_i+1. So it increases with r_i. To maximize sum, we want to allocate the R "remaining seats" to those r_i with the highest marginal gain, i.e., those that already have large r_i. This leads to a "rich get richer" allocation: we give as many remaining seats as possible to the plane with the largest current r_i. Starting with r_i = a_i (if no seats sold), but we have to sell n seats total, so we need to reduce from a_i to r_i. Equivalently, we start with r_i = a_i, and we need to reduce total by n (i.e., we need to subtract n from sum r_i). Reducing a particular r_i by 1 corresponds to selling a seat from that plane, which reduces the convex sum by (r_i) (since the marginal loss is r_i). To minimize revenue, we want to choose which r_i to reduce (i.e., which plane to sell a seat from) such that the total reduction in the convex sum is minimized (since revenue = constant - convex_sum). That is, we want to subtract n times, each time choosing a plane with the smallest current r_i to decrement (because the reduction is r_i). Starting with r_i = a_i. This is exactly the greedy min algorithm: at each step, pick the plane with the smallest current r_i (which equals current empty seats) to sell a seat from, because that causes the smallest reduction in the convex sum, thus maximizing the final convex sum, thus minimizing revenue. So the greedy min is optimal. Perfect!
Thus, we can confidently implement both max and min using heaps.
Implementation details:
- Input n, m.
- Read array a of length m.
- For max: use max-heap (priority queue) containing the current empty seats. Initialize with all a_i. Then for i in 1..n: pop max value x, add x to total_max, if x-1 > 0 push x-1 back.
- For min: use min-heap similarly. But careful: min-heap should contain the current empty seats. However, we need to consider that when we pick a plane with x empty seats, we pay x and then it becomes x-1 (if x>1). But if x-1 > 0 we push back. That's straightforward.
- Edge case: Some a_i may be 0? According to constraints, a_i >=1. So initial seats positive. But after decrement, can become 0; we don't push back 0.
Complexities: O((n+m) log m) which is fine.
Now, test given examples:
Example1: n=4,m=3, a=[2,1,1]. Max: heap max: 2,1,1. Step1: pop 2, sum=2, push 1 -> heap:1,1,1. Step2: pop 1 (max) maybe 1, sum=3, push 0? Actually if x=1, x-1=0 so don't push. heap becomes 1,1. Step3: pop 1 sum=4, push 0 -> heap:1. Step4: pop 1 sum=5. total_max=5. Min: min-heap:1,1,2. Step1: pop 1 sum=1, push 0? if 1 -> no push. heap:1,2. Step2: pop 1 sum=2, heap:2. Step3: pop 2 sum=4, push 1 -> heap:1. Step4: pop 1 sum=5. total_min=5. Output 5 5.
Example2: n=4,m=3, a=[2,2,2]. Max: steps: 2 (push1) sum2; then max among {2,2,1} =2 sum4 push1; then max among {2,1,1} =2 sum6 push1; then max among {1,1,1} =1 sum7 total=7. Min: min-heap:2,2,2. Step1: pop2 sum2 push1 => heap:2,2,1? Actually after push, we have 2,2,1. Step2: min is 1, pop1 sum3, push0? Actually 1-1=0 not push => heap:2,2. Step3: min=2 pop2 sum5 push1 => heap:2,1. Step4: min=1 pop1 sum6 push0 => total=6. So output 7 6. matches.
Thus implementation straightforward.
But note: In min-heap approach, we need to be careful to always pick the smallest current empty seats. That's what we did. However, is there any nuance about ties? Not important.
Thus answer: use two heaps.
Now, we need to write solution in C++ (since typical). But the instruction says "We need to produce final answer". Since the user didn't specify language, but usually we write code in C++ for such problems. But the user said "You are an AI". Possibly they expect solution description? The problem statement is typical from Codeforces (I think). The output is just two numbers.
Thus final answer: Provide code in C++.
But the user might want explanation? The prompt says: "Lolek and Bolek are about to travel... Output Print two integers — the maximum and the minimum number of zlotys that the airport administration can earn, correspondingly." So likely they want a solution. We can produce a C++ program.
We'll implement:
#include #include #include #include using namespace std;
int main() { int n, m; cin >> n >> m; vector a(m); for (int i = 0; i < m; ++i) cin >> a[i];
// Max priority_queue<int> maxHeap; for (int x : a) maxHeap.push(x); long long maxSum = 0; for (int i = 0; i < n; ++i) { int x = maxHeap.top(); maxHeap.pop(); maxSum += x; if (x - 1 > 0) maxHeap.push(x - 1); } // Min priority_queue<int, vector<int>, greater<int>> minHeap; for (int x : a) minHeap.push(x); long long minSum = 0; for (int i = 0; i < n; ++i) { int x = minHeap.top(); minHeap.pop(); minSum += x; if (x - 1 > 0) minHeap.push(x - 1); } cout << maxSum << " " << minSum << endl; return 0;}
But need to use long long because sums can be up to? n up to 1000, a_i up to 1000, maximum total if all seats sold? But n <= 1000, each seat price <= 1000, so max sum <= 1e6, fits in int. But if n=1000 and a_i up to 1000, worst-case: all seats from one plane: sum = 1000+999+...+1 = 500500, still < 2^31. But maybe sum of many planes? Actually n=1000, a_i each up to 1000, but total seats >= n, could be more. But max sum if we always pick highest possible: could be up to ~ (1000 + (1000 - 999)) * 1000/2 = 500500 as said. So int is fine, but safe to use long long.
Now note: In min heap, we should ensure that we always pick the smallest, but note that after we pop smallest x and push x-1 (if >0), the heap property holds. This simulates selling from that plane. This algorithm indeed yields the minimal total? Let's double-check with some more tests, maybe edge cases.
Edge case: n=1,m=1,a=[5] => max=5,min=5.
Edge: n=1000,m=1000, all a_i=1000, total seats=1e6. Then min: greedy will keep picking smallest: initially all 1000, smallest is 1000. It will pick one plane and keep picking from it until it becomes 0? Actually step1: smallest=1000 (any). After picking, becomes 999, push 999. Now heap contains 999 and 999 other 1000s? Actually we removed one 1000 and pushed 999. So the multiset now: 999, and 999 copies of 1000? Wait we had 1000 planes each with 1000. After one pick, we have: one plane now 999, the other 999 planes still 1000. The smallest among these is 999. So we will pick that same plane again? The min-heap will always have the smallest as the one we are decrementing, so yes, it will keep picking from the same plane until it becomes 0. So it will fully exhaust one plane (1000 seats), giving revenue sum 1000+999+...+1 = 500500. Then n=1000, after exhausting one plane we have sold 1000 seats exactly, done. So min sum = 500500. Max sum: will pick largest each time, which will be 1000 always until maybe near the end? Actually max heap: step1 pop 1000, push 999, heap now has many 1000s and one 999. Next pop 1000, push 999, etc. So it will pick from different planes to keep high values. The max sum will be: first 1000 picks all give 1000? But after picking 1000 from a plane, it becomes 999, but there are many 1000 planes, so as long as there are planes with 1000, we pick those. Since we have 1000 planes, each with initial 1000, we can pick 1000 seats all at price 1000 if we pick one seat from each plane. That would yield 1000*1000 = 1,000,000. But is that possible? Yes: each plane we pick only once, so each gives 1000. After picking one from each, all become 999, but we have already taken n=1000 seats, exactly one from each. So max sum = 1,000,000. So min and max differ widely.
Our algorithm for max uses max-heap: it will pick 1000, push 999; then next max is 1000 (from another plane), etc. So after 1000 steps, it will have taken 1000 from different planes (since each time the max is 1000 until we have taken from all). So total = 1000*1000 = 1e6. Good.
Now, test another edge: n=5, m=2, a=[5,5]. Min: greedy picks smallest (both 5), picks one, becomes4, then smallest 4 (same plane), becomes3, then 3, then 2, then 1? Actually need 5 picks. Starting both 5. step1: pick 5 -> becomes4. heap:5,4. step2: min=4 -> pick4 -> becomes3. heap:5,3. step3: min=3 -> pick3 -> becomes2. heap:5,2. step4: min=2 -> pick2 -> becomes1. heap:5,1. step5: min=1 -> pick1 -> becomes0. total=5+4+3+2+1=15. This is same as using one plane fully. Max: picks 5,5,5,5,5? Actually with two planes: step1: pick5 -> push4 -> heap:5,4. step2: max=5 -> pick5 -> push4 -> heap:4,4,? Actually after step2, we have two 4's? Let's simulate: start: [5,5]. step1: pop5 (say plane1) -> push4 -> now [5 (plane2),4]. step2: pop5 (plane2) -> push4 -> now [4,4]. step3: pop4 -> push3 -> [4,3]. step4: pop4 -> push3 -> [3,3]. step5: pop3 -> push2 -> [3,2]. Total = 5+5+4+4+3 = 21. This matches taking 2 seats from each? Actually allocation: k1=3? Let's compute: After step1: k1=1, a1=4; step2: k2=1, a2=4; step3: pick from which? In our simulation step3 we popped 4 (could be from either). Suppose it's from plane1: then k1=2, a1=3. step4: popped 4 from plane2: k2=2, a2=3. step5: popped 3 from plane1: k1=3, a1=2. So total revenue = f1(3)=5+4+3=12, f2(2)=5+4=9 total=21. That's max. So algorithm works.
Now, what about scenario where after some steps, the min-heap might have a zero? But we never push zero, so only positive numbers. So no issue.
Thus, answer is correct.
Implementation details: Use long long for sum.
Now, might there be any nuance: The problem says "it is up to a passenger to choose a plane to fly on; if the chosen plane has x (x > 0) empty seats at the given moment, then the ticket for such a plane costs x zlotys". So the passengers may choose arbitrarily. We are asked maximum and minimum that airport can earn. So our greedy algorithms for max and min correspond to the best/worst-case choices for the airport. However, note: The passengers are the ones choosing. The airport would earn maximum if passengers choose planes in a way that maximizes revenue; but would passengers want to maximize revenue? Usually not, they might want to minimize their own cost. But the problem statement says "what is the maximum and the minimum number of zlotys the airport administration can earn?" It doesn't say passengers are cooperating with airport; it's about the possible range. So it's the set of all possible outcomes given passengers can choose any plane at each step. So the max is the best-case for airport (if passengers happen to choose in a way that maximizes revenue), and min is the worst-case for airport (if passengers choose to minimize revenue). Since passengers likely want to pay less, the min is the more plausible scenario, but we compute both.
Thus solution stands.
Now, check constraints: n,m up to 1000, a_i up to 1000. So we can also implement using multiset or sorting each time. But heap is efficient.
One more nuance: For min, we might also consider that after we pick a plane with x empty seats, we pay x, then it becomes x-1. If x-1 > 0, we push it back. But is it always optimal to pick the smallest? Let's test a scenario where picking the smallest might lead to a later larger value that could have been avoided by picking a slightly larger one now. For example, a = [3,3], n=3. Greedy min: pick 3 -> becomes2, then pick2 -> becomes1, then pick1 -> total=3+2+1=6. Alternative: pick 3 from first (3), then pick 3 from second (3), then pick 2 from first (2) total=3+3+2=8 >6. So min is 6. Good.
a = [4,2,2], n=4. Greedy min: pick 2 (one of the 2) -> becomes1; pick 1 -> becomes0; pick 2 (the other 2) -> becomes1; pick 1 -> total=2+1+2+1=6. Alternative: pick 2, then 2 (the other 2), then 2? Actually after picking one from each 2, we have both become 1. Then remaining picks would be from 4 or from those 1s. If we pick from 4: say sequence: 2,2,4,1 =9. Or 2,2,1,1 =6 same. So min=6. So ok.
Now consider a scenario where there are many planes with capacity 1, and one with capacity large. For min, we should pick the capacity-1 planes first because they cost 1. That's what greedy does.
Thus algorithm is solid.
Now, just implement.
Potential pitfalls: Use of priority_queue in C++: For max, default is max-heap. For min, we can use greater. Also, push initial values.
Now, note: The total number of seats may be larger than n, but we only sell n seats. The heap simulation will stop after n steps; we don't care about remaining.
Time complexity: O(n log m) which is fine.
Now, let's produce final answer.
But the user might want explanation. However, the problem statement is from some contest; typical solution is using priority queue. I'll output the code.
But the prompt says "Lolek and Bolek are about to travel..." and then Input, Output, examples. The user might be expecting a solution in the form of a program. Since this is a text response, I'll provide the code with explanation.
Given that this is an assistant answer, I'll respond with a detailed explanation and the code.
Thus final output:
We'll provide a C++ solution. ```cpp
#include #include #include #include // for greater
using namespace std;
int main() { int n, m; cin >> n >> m; vector a(m); for (int i = 0; i < m; ++i) cin >> a[i];
// ----- maximum revenue ----- priority_queue<int> maxHeap; // default max‑heap for (int x : a) maxHeap.push(x); long long maxSum = 0; for (int i = 0; i < n; ++i) { int x = maxHeap.top(); maxHeap.pop(); maxSum += x; if (x - 1 > 0) maxHeap.push(x - 1); } // ----- minimum revenue ----- priority_queue<int, vector<int>, greater<int>> minHeap; // min‑heap for (int x : a) minHeap.push(x); long long minSum = 0; for (int i = 0; i < n; ++i) { int x = minHeap.top(); minHeap.pop(); minSum += x; if (x - 1 > 0) minHeap.push(x - 1); } cout << maxSum << " " << minSum << endl; return 0;}