It's another Start[c]up finals, and that means there is pizza to order for the onsite…
- User
It's another Start[c]up finals, and that means there is pizza to order for the onsite contestants. There are only 2 types of pizza (obviously not, but let's just pretend for the sake of the problem), and all pizzas contain exactly S slices.
It is known that the i-th contestant will eat si slices of pizza, and gain ai happiness for each slice of type 1 pizza they eat, and bi happiness for each slice of type 2 pizza they eat. We can order any number of type 1 and type 2 pizzas, but we want to buy the minimum possible number of pizzas for all of the contestants to be able to eat their required number of slices. Given that restriction, what is the maximum possible total happiness that can be achieved? Input
The first line of input will contain integers N and S (1 ≤ N ≤ 105, 1 ≤ S ≤ 105), the number of contestants and the number of slices per pizza, respectively. N lines follow.
The i-th such line contains integers si, ai, and bi (1 ≤ si ≤ 105, 1 ≤ ai ≤ 105, 1 ≤ bi ≤ 105), the number of slices the i-th contestant will eat, the happiness they will gain from each type 1 slice they eat, and the happiness they will gain from each type 2 slice they eat, respectively.
Output
Print the maximum total happiness that can be achieved.
Examples
Input
3 12 3 5 7 4 6 7 5 9 5
Output
84
Input
6 10 7 4 7 5 8 8 12 5 8 6 11 6 3 3 7 5 9 6
Output
314
Note
In the first example, you only need to buy one pizza. If you buy a type 1 pizza, the total happiness will be 3·5 + 4·6 + 5·9 = 84, and if you buy a type 2 pizza, the total happiness will be 3·7 + 4·7 + 5·5 = 74.
Assistant
We need to parse the problem: There are N contestants, each will eat exactly si slices. We can order pizzas of two types (type1 and type2). Each pizza has exactly S slices. We can order any number of each type. However, we want to buy the minimum possible number of pizzas to satisfy the total slices needed by contestants. That is, we need to cover the total slices sum_{i=1..N} si with a number of pizzas (each provides S slices) such that the total number of pizzas is minimized. Obviously the minimum number of pizzas is ceil(total_slices / S). Because we can mix types? But careful: The pizza types are distinct in the sense that each pizza is either type1 or type2, and each slice from that pizza is of that type. But contestants can have slices from different pizzas? Essentially we are allocating slices to contestants; each slice a contestant eats is either type1 or type2, and the happiness they get per slice depends on the type. So the total happiness sum_i (xi * ai + (si - xi) * bi) where xi is number of type1 slices eaten by contestant i, 0 <= xi <= si. But also there is a global constraint: The total number of type1 slices used must be <= number of type1 pizzas * S, similarly for type2. And total number of pizzas = (#type1 + #type2) must be exactly the minimum number needed: ceil(T/S) where T = total slices required. So we cannot just arbitrarily choose any mixture; we must choose a number of type1 pizzas (call P1) and type2 pizzas (P2) such that P1 + P2 = M = ceil(T/S). And we must be able to allocate slices: the total type1 slices allocated <= P1S, total type2 slices allocated <= P2S, and the sum of allocations = T. Because we can have leftover slices if total capacity exceeds demand; but since we are minimizing number of pizzas, total capacity M*S is at least T, but may be greater; we could have waste. But we can have leftover slices unused (like uneaten pizza slices). The problem says: "buy the minimum possible number of pizzas for all of the contestants to be able to eat their required number of slices." So we are restricted to buying exactly M pizzas (or at most M? It says minimum possible number, so we must buy that number to satisfy the requirement; we could buy more but that would not be minimal; so we must buy exactly M pizzas? Actually "we want to buy the minimum possible number of pizzas for all of the contestants to be able to eat their required number of slices." So we are looking for the maximum happiness given that we buy the minimal number of pizzas. That means we are constrained to use at most the minimum number of pizzas? Or we must exactly use that number because if we buy more, it's not minimal. But the problem might read: "Given that restriction, what is the maximum possible total happiness that can be achieved?" So we must choose to buy exactly M pizzas (the minimal number). Because if we bought more, we wouldn't be respecting the "minimum possible number" restriction; we want to achieve the maximum happiness among all ways that use the minimum number of pizzas. So we have to allocate exactly M pizzas, with types chosen arbitrarily.
So we need to choose P1, P2 >= 0 integers with P1+P2 = M. Then we need to allocate xi for each contestant, with sum_i xi = X (total type1 slices used), and sum_i (si - xi) = T - X = Y (type2 slices). And we must have X <= P1S, Y <= P2S. Since T <= M*S, it's possible that X and Y can be satisfied if we pick appropriate P1,P2. Note we can have waste; leftover slices of either type are fine.
Goal: maximize total happiness sum_i [xiai + (si - xi)bi] = sum_i sibi + sum_i xi(ai - bi). Let C = sum_i sibi (constant). So maximizing total happiness is equivalent to maximizing sum_i xi(ai - bi). So define di = ai - bi. Then we want to assign xi (0 <= xi <= si) to maximize sum xi di, subject to constraints on total type1 slices X = sum xi and type2 slices Y = T - X, and that there exists P1,P2 >=0 integer with P1+P2 = M, X <= P1S, Y <= P2S.
Given M and S, what constraints on X are possible? For some P1, we have capacity for type1: P1S, and for type2: (M-P1)S. The constraints are X <= P1S and T - X <= (M-P1)S, i.e., X >= T - (M-P1)S = T - MS + P1S. Since T <= MS, T - MS <= 0. So lower bound: X >= T - (M-P1)S = T - MS + P1S = P1S - (MS - T). Define W = MS - T, the total waste (slices we will not eat, but capacity minus demand). W is between 0 and S-1 inclusive (since M = ceil(T/S), MS - T < S). So constraints: For a given P1, we must have X in the interval: [max(0, P1S - W), min(P1S, T)]? Let's derive precisely:
We need X <= P1S and Y = T - X <= (M-P1)S => T - X <= (M-P1)S => X >= T - (M-P1)S = T - MS + P1S = P1S - (MS - T) = P1*S - W.
Also X >= 0 and X <= T (since it's sum of slices). So the feasible X for given P1 is in the interval:
Lower = max(0, P1S - W) Upper = min(P1S, T)
And also we need that Lower <= Upper. This holds if P1S - W <= P1S (always) and also max(0, P1S - W) <= min(P1S, T). For P1S - W may be negative, then lower is 0. For P1S >? Actually, we must also have P1S - W <= T (since upper bound min(P1S, T) <= T). Condition: P1S - W <= T (i.e., P1S <= T+W = MS). That's true because P1 <= M => P1S <= MS = T+W. Also need that 0 <= min(P1S,T) etc. So feasible interval is non-empty as long as Lower <= Upper. Let's check: if P1S - W <= P1S obviously, and we need that max(0, P1S - W) <= min(P1S, T). The worst case is when max(0, P1S - W) > min(P1S, T). Could happen if P1S - W > T (then max is P1S - W, min is T, so condition fails). But P1S - W > T => P1S > T+W = MS, impossible since P1 <= M, so P1S <= MS = T+W. So always P1S - W <= T. Also if P1S - W > P1S? No. So interval is non-empty.
Thus for any P1 in [0..M], X must be in that interval. Conversely, given an X (total type1 slices allocated), is there a P1 such that these constraints hold? We want to know the set of feasible X values achievable by some choice of pizza types count. Since we can choose P1 arbitrarily as long as P1+P2=M, the overall feasible X values across all P1 is:
Feasible X = Union_{P1=0..M} [max(0, P1S - W), min(P1S, T)].
We need to find X that is achievable, then maximize sum_i xi di, where sum xi = X and 0 <= xi <= si. The choice of xi is independent of P1 as long as X is feasible; then we can choose P1 accordingly. So the problem reduces to: find an integer X (0 <= X <= T) such that X is in the union above, and we can assign xi to achieve that X maximizing the sum of di*xi. And we want the maximum possible happiness overall.
But note that the assignment of xi to achieve a given total X and maximize sum di*xi is a classic: we want to allocate X type1 slices to contestants where each slice assigned to contestant i gives marginal happiness di (since each slice gives di extra over type2). However, each contestant i can receive at most si type1 slices (and also at least 0). If we treat each slice as an item (like we have si copies from contestant i each with value di), then to maximize sum of values for exactly X slices, we would assign slices to highest di values. However, there is a twist: The xi for each contestant is the number of type1 slices they eat; all slices are independent? Since the happiness per slice for type1 is ai, per slice for type2 is bi, and di = ai - bi. So if we assign a slice to contestant i as type1, we gain di compared to if it were type2. So for a fixed total X, the maximum total extra happiness is the sum of the largest X di values among all "slice slots" (considering each contestant provides si copies of di). Because we can freely assign which slices are type1, subject to each contestant's si limit. So indeed, we sort all "slice units" by di descending, and we take the top X units. That's the optimum for given X.
But we also need to ensure that the total type2 slices T-X does not exceed capacity? Already accounted via X feasibility.
Thus the total maximum happiness for a given X is: Total = C + sum_{top X di} di, where C = sum_i si*bi.
Now, X must be such that it's possible to allocate exactly X type1 slices given the pizza constraints (i.e., X is in the feasible set described). Since we can choose P1 accordingly, we need to consider the set of X that can be realized with exactly M pizzas.
Now we need to find the maximum over X in feasible set of (C + sum of top X di). Since C is constant, maximize sum of top X di.
Observation: The feasible set of X is all integers X such that there exists integer P1 with 0 <= P1 <= M satisfying:
P1S - W <= X <= P1S and also 0 <= X <= T. But note: Because of upper bound min(P1S, T), which for P1S <= T, upper is P1S; for P1S > T, upper is T. But note that T = MS - W, and P1S > T means P1S > MS - W => (M-P1)S < W, but P1 <= M. Since W < S, it's possible only when P1 = M? Let's examine: For P1 = M, P1S = MS = T+W, so it's > T. Then min(P1S, T) = T. So for P1=M, the upper bound is T. For P1=M-1, (M-1)S = MS - S = T+W - S. Since W < S, this is <= T? T = MS - W => (M-1)S = MS - S = T + W - S. Compare to T: T+W-S <= T? Yes if W - S <=0, which is true because W < S, so T+W-S < T. So for P1=M-1, P1S <= T (since (M-1)S <= T? Actually need to check if (M-1)S <= T. (M-1)S = MS - S = T+W - S. Since W <= S-1, we have T+W-S <= T + (S-1) - S = T-1 < T. So yes < T. So for all P1 <= M-1, P1S <= T. So min(P1S, T) = P1*S for P1 <= M-1. For P1=M, it's T.
Similarly, lower bound: max(0, P1S - W). For P1 such that P1S >= W, then lower = P1S - W; else lower = 0. Since W < S, for P1=0: 0S - W = -W -> max(0, -W)=0. For P1=1: if S >= W? Possibly S > W always? W < S, so 1S - W > 0 if S > W. Since S >=1 and W < S, yes S - W > 0? Actually if S > W then positive. If S = W? W < S, so cannot equal. So for P1 >=1, P1S - W >= S - W > 0, so lower = P1*S - W.
Thus the intervals:
For P1 = 0: [0, 0]? Actually min(P1S, T) = 0, so X in [0,0] i.e., X=0 only feasible? But also need to satisfy X >= P1S - W = -W => 0, so X=0. For P1 from 1 to M-1: X in [P1S - W, P1S] (since min = P1S, lower = P1S - W >0). Note that this interval length is exactly W (since from P1S - W to P1S inclusive, there are W+1 integer points? Actually inclusive integer interval length = W+1? If we consider integer X, the number of integers between L and U inclusive is U-L+1 = (P1S) - (P1S - W) + 1 = W+1. So each such P1 gives a block of W+1 possible X values: from P1S - W to P1S inclusive.
For P1 = M: X in [MS - W, min(MS, T)] = [T, T] because M*S - W = T, and min = T, so X = T only.
Thus the feasible set of X is: X=0, X=T, and for each integer p from 1 to M-1, X in [pS - W, pS] (which are integer intervals). But careful: There could be overlaps between intervals for different p. Since p ranges, these intervals may be contiguous? Let's see: For p, interval is [pS - W, pS]. For p+1, interval is [(p+1)S - W, (p+1)S]. The gap between pS and (p+1)S - W: (p+1)S - W - pS = S - W. Since S > W (as W < S), S - W >= 1. So there is a gap of size S - W - 1? Actually integer points: The next interval starts at (p+1)S - W, which is pS + S - W. The previous interval ends at pS. So the smallest integer not covered by p interval is pS+1. The next interval starts at pS + S - W. So if S - W > 1, there is a gap of integers from pS+1 to pS+S-W-1 inclusive. For example, S=12, W=... say T=?, M=ceil(T/12). For first sample, N=3, S=12, s:3+4+5=12, T=12, M=1, W=0. Then M-1=0 so no intervals, only X=0 and X=T? But M=1 only p=0 and p=1? Actually p from 1 to M-1 inclusive; if M=1, then no p. So feasible X = 0 and 12. That matches: we can order one pizza; either all type1 (X=12) or all type2 (X=0). So answer is max of those.
For M > 1, we have multiple intervals with gaps. So X must lie within these intervals. But is there any other possibility? The union also includes X=0 and X=T.
Now note that T = M*S - W, and W < S. So the intervals for p = 1,..., M-1 are within the range from S - W to (M-1)S. Does that cover all X? Let's check endpoints: p=1 gives [S-W, S]; p=M-1 gives [(M-1)S - W, (M-1)S]. The full range of possible X (0 to T) is covered? Possibly not; there are gaps.
Thus the problem reduces to selecting X from the set: {0, T} ∪ (union over p=1..M-1 of integer X in [pS - W, pS]). This set is not all integers from 0 to T; there are forbidden gaps.
We want to maximize sum of top X di. Since the sum of top X di as function of X is increasing (since di can be negative? Wait di can be negative because ai, bi are positive but ai could be less than bi; so di may be negative. The sum of top X di is not necessarily monotonic non-decreasing: If we take more slices, we might be forced to include negative di values, so the total extra happiness could decrease. However, we are free to choose any X (subject to constraints) and allocate slices accordingly. The function f(X) = sum of top X di (i.e., sum of X largest di values among all slice-units) is a concave? Actually it's the prefix sum of sorted di values (descending). Let the multiset of all di values (with multiplicities si) be sorted decreasing: v1 >= v2 >= ... >= v_T (total T entries). Then f(X) = sum_{j=1}^{X} v_j. This is a non-decreasing function? Since v_j can be negative; but if we include negative ones, f(X) could be lower than f(X-1) if v_X is negative? Wait sum_{j=1}^{X} v_j = f(X-1) + v_X. Since v_X could be negative, f(X) could be less than f(X-1). But we are allowed to choose X=0 as well. So we want to maximize f(X) over allowed X, not necessarily the maximum X. So we must consider possibly not taking all slices as type1 if the extra ones are detrimental.
But careful: The total happiness is C + f(X). Since C is constant, maximizing total happiness is equivalent to maximizing f(X). So we need to find the best X in the feasible set.
Now, T can be up to sum si up to? N up to 1e5, each si up to 1e5, so total T could be up to 1e10? Actually N * si max: N=1e5, each si up to 1e5, total T up to 1e10 which is too large to enumerate slices individually. But we need to handle efficiently.
Observation: The di values per contestant come in groups: for each contestant i, we have si copies of value di. So we can think in terms of sorting by di. We need to compute f(X) for many X values that are in the feasible set. The feasible set consists of intervals of length W+1 for p from 1 to M-1, plus endpoints 0 and T. W = M*S - T, and M = ceil(T/S). Since S up to 1e5, and T up to 1e10, M could be as large as 1e5? Actually T up to 1e10, S min 1 => M up to 1e10? That's huge. But N is 1e5, but sum si could be huge. So we cannot iterate over M, which could be up to 1e10. However, we can think differently: The constraints are such that the number of pizzas M is large potentially, but note that N is only 1e5, and each si ≤ 1e5, but sum could be up to 1e10, which is large. However, we cannot have M huge and then iterate over all p from 1..M-1. We need a more clever approach.
Let's examine the feasible X intervals: X in [pS - W, pS] for p integer. That's essentially X modulo S? Because these intervals are aligned to multiples of S. Specifically, X = pS - k, where 0 <= k <= W. So feasible X are those integers X such that when we divide by S, the quotient floor(X/S) = p, and the remainder r = X mod S, we require that r >= S - W? Actually X = pS - k, with k from 0 to W, so remainder = pS - k mod S = (-k) mod S = S - k if k>0 else 0. So remainder can be S, S-1, ..., S-W? But mod S, remainder 0 corresponds to k=0; remainder S-1 corresponds to k=1; remainder S-W corresponds to k=W. So the feasible X (excluding X=0 and X=T) are those with remainder in [S-W, S] inclusive (where remainder = 0 is also allowed but note that remainder 0 only when k=0, i.e., X = pS exactly, which is included as long as p from 1..M-1. Also remainder S corresponds to? Actually remainder ranges 0..S-1 normally. S mod S = 0. So remainder = 0 (k=0) gives X = pS, which is within [pS-W, pS]. So we can describe feasible X (excluding endpoints) as: X is an integer multiple of S (pS) or X is just below a multiple of S by at most W. More precisely: X mod S is in {0} ∪ {S-W, S-W+1, ..., S-1}? Actually for k from 0 to W, remainder = (-k) mod S. When k=0, remainder 0. For k=1, remainder S-1; for k=2, remainder S-2; ... for k=W, remainder S-W. So feasible remainders are: 0, S-1, S-2, ..., S-W. That's a set of size W+1. So feasible X are those integers between 0 and T such that X mod S ∈ R, where R = {0} ∪ {S-W, S-W+1, ..., S-1}. But note that for X=0 it's already included as remainder 0, but X=0 is also in R? Yes remainder 0, but X=0 corresponds to p=0? Actually for p=0, X=0 is in the set. For X=T, T = MS - W, so its remainder = (MS - W) mod S = (-W) mod S = S - W (if W>0) or 0 if W=0. So remainder of T is also in R. So the entire feasible set can be described as: X integer, 0 ≤ X ≤ T, and X mod S ∈ R, where R = {0} ∪ [S-W, S-1] (if W > 0). If W = 0, then R = {0} only? Because W=0 means no waste, T = MS exactly, then intervals: for p=1..M-1, X ∈ [pS, pS] (since W=0, interval is just {pS}), and X=0, X=T=MS also multiple of S. So indeed R = {0}. So overall, feasible X are exactly those X in [0, T] whose remainder modulo S belongs to R.
Check: For W > 0, R includes 0 and the top W remainders: S-W to S-1. Indeed, that matches the union of intervals. Let's verify that no other X can be feasible. For a given X, suppose we set P1 = ceil(X/S)? Actually we derived necessary and sufficient condition from existence of P1: ∃ integer p (0≤p≤M) such that pS - W ≤ X ≤ pS and X ≤ T. This is equivalent to: There exists integer p such that pS is the nearest multiple of S above or equal? Let's transform: Condition: ∃ p with X ≤ pS ≤ X+W? Because pS - W ≤ X ≤ pS implies pS is between X and X+W? Actually from pS - W ≤ X => pS ≤ X+W; and X ≤ pS => pS ≥ X. So ∃ integer p such that X ≤ pS ≤ X+W. And also p ≤ M (since p from 0..M) but also p must be such that pS ≤ MS? Actually p ≤ M automatically if pS ≤ MS? However, we also need p ≥ 0 and p ≤ M. The condition X ≤ T ensures that if we find p with X ≤ pS ≤ X+W, does it automatically satisfy p ≤ M? Since pS ≤ X+W ≤ T+W = M*S, so p ≤ M. Also p ≥ 0 obviously. So feasible X are those integers for which there exists an integer multiple of S between X and X+W (inclusive). That's a neat characterization.
Thus, X is feasible iff there exists integer k such that kS ∈ [X, X+W]. In other words, the distance from X up to the next multiple of S is ≤ W (including possibly being exactly at a multiple). Let r = X mod S, i.e., X = qS + r, with 0 ≤ r < S. Then the next multiple after X is (q+1)S if r > 0, or X itself if r=0. The condition: there exists p such that pS ∈ [X, X+W]. That p could be q if r=0 (then pS = X). If r>0, then the smallest multiple ≥ X is (q+1)S = qS + S. So condition becomes (q+1)S ≤ X+W => S - r ≤ W => r ≥ S - W. So indeed, if r = 0, always feasible; if r > 0, feasible iff r ≥ S - W.
Thus the feasible X are exactly those where X mod S = 0 or X mod S ≥ S - W. Equivalent to remainder in R as above.
Now, we need to maximize f(X) over X in 0..T with that remainder condition.
Now, T can be huge (up to 1e10), but N is only 1e5, and each si up to 1e5. The di values can be positive, negative, zero. We need to compute f(X) efficiently for many X, but we only need to consider X values that satisfy the remainder condition. However, there could be many such X: number of feasible X is roughly (M)(W+1) ≈ (T/S)(W+1). Since W+1 <= S, the number of feasible X is about (T/S)S = T? Actually number of integers between 0 and T with remainder in R is approximately (T+1) * (|R|/S) = (T+1)(W+1)/S. That could be as large as T when W+1 is close to S (i.e., W = S-1, then all remainders except maybe some? Actually if W = S-1, then R = {0} ∪ [1, S-1] = all remainders. So all X are feasible! That would be worst-case where the waste W = S-1, meaning total slices T = M*S - (S-1) = (M-1)S +1, so the total capacity exceeds demand by S-1 slices. In that case, any X between 0 and T is feasible? Let's check: condition r=0 or r ≥ S-W = S-(S-1)=1. That's all remainders r≥0? Since r≥0 always. Actually S-W =1, so condition: r=0 OR r≥1 => r any (0..S-1). So yes, all X feasible. So in the worst case, the feasible set is all integers from 0 to T. Then we need to maximize f(X) over all X. That could be large, but T up to 1e10 makes enumerating all X impossible.
But perhaps we can find a structural property that the optimal X is either 0, T, or some boundary points, or that f(X) is concave or something that lets us find maximum without scanning all.
Let's analyze f(X) = sum of top X di values. This is essentially the prefix sum of sorted list of values. The sorted list (descending) can be thought of as a sequence of values, possibly with repeated groups (since each contestant contributes si copies of di). Let's denote we have a multiset of values with frequencies. We can sort the unique di values. Let there be K distinct di values, each with total count cnt_j. Sorted descending: d(1) > d(2) > ... > d(K). (We could also have equal values, but we can treat them as one group). Then f(X) as a function is piecewise linear: it increases by d(1) per slice while X is within first cnt_1, then by d(2) for next cnt_2, etc. So f(X) is a concave? Actually derivative (increment per unit) is non-increasing because d values are descending. So f is a concave (discrete) function: f(X+1) - f(X) is non-increasing as X increases. Because the marginal gain when adding the (X+1)-th slice is the next value in sorted order, which is non-increasing. So f is a concave function (in the sense of discrete concave: f(x+1) - f(x) is decreasing). That's important.
Now we want to maximize f(X) over allowed X. Since f is concave, its maximum over a convex set of integers (like an interval) would occur at an endpoint if the function is monotonic? Actually for concave function, maximum over an interval is at the boundaries if the function is decreasing after a point? Wait: A concave function has the property that any local maximum is a global maximum over the entire domain, but over a restricted domain, the maximum is at the boundaries if the function is decreasing throughout or increasing? Let's recall: For a concave function, the maximum over a closed interval is attained at one of the endpoints if the function is concave and has no interior point with derivative zero? Actually consider f(x) = - (x-5)^2, which is concave. Over interval [0,10], maximum is at x=5, which is interior. So concave functions can have interior maxima. But note that - (x-5)^2 is concave, maximum at interior. So concave does not guarantee endpoints. However, f here is defined on integers and its discrete differences are decreasing. This is a "unimodal" function? Not necessarily; if marginal gains start positive then become negative, f increases then decreases, so it has a single peak. Because the increments are non-increasing; if they start positive and eventually become negative, f will increase until the point where increment becomes negative, then decrease. So f will be unimodal: it rises while marginal > 0, then after marginal becomes ≤ 0, it declines (or stays flat if zero). So f has a maximum at some X*: the point where cumulative sum is largest. Usually X* is the smallest X such that marginal becomes negative? Actually if marginal are positive then zero then negative, the maximum could be at the point before first non-positive marginal? Let's be precise: Let v1 >= v2 >= ... >= v_T. Define f(0)=0. The increment at step t: Δf(t) = v_t (for t from 1 to T). Since Δf is non-increasing, as we increase X, f increases while Δf > 0, then if Δf becomes zero, f stays constant, then if Δf becomes negative, f decreases. So the set of X that maximize f is a (possibly interval) where Δf >= 0 and next Δf <= 0? Actually the maximum is achieved at any X where all taken v's are non-negative and all not taken are non-positive? More clearly, f(X) is maximal when adding another slice would decrease f (i.e., v_{X+1} < 0) and removing a slice would decrease f (i.e., v_X > 0). So the optimal X is the number of positive v's, but if there are zeros, any number of zeros can be included or excluded without changing f. So the maximum value is sum of all positive v's (plus possibly zeros). So the maximum over all X (without restrictions) is sum_{v_i > 0} v_i (plus maybe zeros). So unrestricted optimum X* would be the count of positive v_i. But with restrictions, we may not be able to achieve that exact X, so we might have to take a nearby feasible X.
Thus we need to find feasible X close to the ideal count of positive di.
Now, the feasible X are those satisfying the modulo condition. This set is not contiguous generally; but for large S and W, it could be dense. The maximum of a concave unimodal function over a set that is not necessarily contiguous can be found by checking the feasible X near the unconstrained optimum, but not necessarily; we might need to consider several candidate X.
Because f is concave and unimodal, its values decrease as we move away from the optimal X (in either direction) if the marginal values are strictly decreasing. However, there may be flat regions if there are ties. But still, the set of X achieving maximum is an interval (maybe a single point). So to maximize over a set of allowed X, we can consider the allowed X that are closest to the unconstrained optimum interval.
Thus, the problem reduces to: compute the unconstrained optimum X0 = the number of positive di? Actually we need to consider also zeros: including zeros doesn't change f, so if there are zeros, any X in [L, R] might yield same max, where L = number of strictly positive, R = number of non-negative? Let's define: let P = number of di > 0, Z = number of di = 0, N = number of di < 0. Then f(X) = sum of top X. For X <= P, all taken are positive; f increases with X. For X between P and P+Z, adding zeros doesn't change f (since zero). So f is constant on [P, P+Z] if we have zeros. For X > P+Z, we start adding negatives, f decreases. So the maximum value is sum of all positive di, and any X in [P, P+Z] attains that maximum (if zeros present). If no zeros, then only X = P attains maximum (assuming no zero). If there are positive and negative but no zero, maximum at X=P.
Thus unconstrained optimal X set is an interval [L_opt, R_opt] where L_opt = # positive di, R_opt = # non-negative di (i.e., positive + zero). If there are both positive and zero, it's an interval; otherwise it's a point.
Given the feasible X set described by remainder condition, we need to find a feasible X that yields maximum f(X). Since f is unimodal and non-decreasing until L_opt and non-increasing after R_opt, the maximum over a set of X is attained at the feasible X closest to the optimal interval, but we need to be careful: if there is a feasible X inside [L_opt, R_opt], then that's optimal. If not, then the best feasible X will be either the largest feasible X ≤ L_opt (if L_opt > 0) or the smallest feasible X ≥ R_opt (if R_opt < T) whichever gives higher f. But since f is increasing up to L_opt and decreasing after R_opt, the best among those would be the one with f highest, which is either at the left side boundary or right side boundary.
Thus we need to compute:
- The sorted list of di values with frequencies.
- Compute prefix sums of sorted di (descending) to evaluate f(X) for any X quickly, if we can compute sum of top X di efficiently using something like binary search on cumulative counts and precomputed prefix sums.
But we also need to compute the feasible X set condition: X mod S ∈ R (R = {0} ∪ [S-W, S-1]) (including 0 and T automatically). So we need to check if there exists an integer X in [L_opt, R_opt] satisfying that condition. If yes, answer is sum of positives (plus zeros if included? Actually sum of non-negatives? Wait maximum f is sum of positive only; zeros add nothing, so f(L_opt) = sum positives; f(R_opt) = sum positives (since zeros add 0). So any X in that interval gives same max. So if any feasible X falls within that interval, answer is sum positives + C.
If not, we need to find best feasible X either less than L_opt or greater than R_opt. Since f is increasing for X<L_opt and decreasing for X>R_opt, the best among feasible X less than L_opt is the maximum feasible X in [0, L_opt-1] (since as X increases, f increases up to L_opt). So we want the largest feasible X ≤ L_opt-1? Actually f is increasing up to L_opt, so the maximum among X ≤ L_opt-1 is at the largest X in that range. So we want max feasible X such that X ≤ L_opt-1 (or ≤ L_opt? But L_opt itself is not feasible if not in set; we are considering X < L_opt). So we need the largest feasible X less than L_opt.
Similarly, for X > R_opt, f is decreasing as X increases, so the best among X ≥ R_opt+1 is the smallest feasible X greater than R_opt. So we need the smallest feasible X greater than R_opt.
Then compare f of these two candidate X (and also possibly X=0 or X=T if not covered) and pick the maximum.
Thus we need to be able to compute:
- L_opt = number of di > 0.
- R_opt = number of di ≥ 0 (i.e., non-negative). Actually careful: di can be zero; including zero doesn't change sum, so f(X) = sum positives for any X in [P, P+Z]. So R_opt = P+Z (count of non-negative). However, is it possible that including some negative values could still yield same sum if they sum to zero? That would be unusual because negatives are negative; including any negative reduces sum. So the only plateau is due to zeros. So indeed.
But also note that there might be a scenario where all di are negative; then the optimal X is 0 (since f(X) is decreasing from start). Then L_opt = 0 (since no positive) and R_opt = number of zeros? Actually if all di are negative or zero: If there are zeros, then including zeros gives same sum as 0? f(0)=0; f(X) for X up to count of zeros is still 0 because zeros add 0. So maximum f is 0, achieved for any X in [0, Z] (if only zeros). If there are negatives and zeros, maximum is 0 and achieved for X=0 up to Z. So the optimal interval includes 0. So we must handle that.
Thus the general approach: Determine the interval [L_opt, R_opt] of X that maximize f(X) (unconstrained). Actually note: If there are positive di, f(0) is less than sum positives. So the maximum is sum positives. That is attained at any X that includes all positives and no negatives. That's exactly X in [P, P+Z] as argued. So the optimal interval is [P, P+Z] (where P = count positive, Z = count zero). If there are no positives, then maximum is 0, and it's attained at any X from 0 up to Z (since adding zeros doesn't change). Actually also if there are negatives only, then f(X) <= 0, and f(0)=0, so 0 is max; and if there are zeros, any X <= Z gives 0. So the optimal interval is [0, Z] in that case (since including zeros yields 0, but also excluding all yields 0). That's consistent if we define P=0, then [0, Z] = [P, P+Z]. If there are both positives and zeros, [P, P+Z] is correct. If there are positives and no zeros, then Z=0, so interval is [P, P] (single point). So we can define P = count of di > 0, Z = count of di == 0. Then the unconstrained optimal set is [P, P+Z] (provided we consider that f(X) = sum of positives for any X in that interval). If there are no positives and no zeros (all negative), then P=0, Z=0, interval would be [0,0] (just X=0). Actually that fits: [P, P+Z] = [0,0]. So general formula works.
But we must be careful: What if there are positives and zeros, but also if we take X less than P, we miss some positive di; that sum is less. If we take X > P+Z, we include negative di, sum decreases. So indeed.
Now we need to check if there exists X in [P, P+Z] that is feasible (i.e., X mod S ∈ R). If yes, answer = C + sum_{di>0} di (since sum of positives). If not, we need to find best feasible X below P or above P+Z.
However, it's also possible that the optimal X is 0 or T if they are included? But those will be considered when we check below/above. Since we consider max feasible X ≤ P-1, which could be 0 if none other. And min feasible X ≥ P+Z+1, which could be T if that's feasible? But T may be > P+Z. So we include.
Now the main challenge: we need to compute f(X) for specific X values, but we may need to compute f for at most two X (the candidate below and above). However, determining the largest feasible X ≤ P-1 and smallest feasible X ≥ P+Z+1 may require some arithmetic, but not iteration over all X because we have the condition modulo S. We can compute these directly.
We also need to compute sum of top X di efficiently for arbitrary X up to T ~ 1e10. Since T can be large, we cannot generate the full sorted list. But we have N groups with frequencies si and values di. So we can sort the groups by di. Let there be K distinct di values, sorted descending: d1 > d2 > ... > dK, with counts c1, c2, ..., cK. Then prefix sums: prefix_counts up to i, and prefix_sum of values (d_i * c_i). For a given X, we can binary search on the prefix_counts to find which group it falls into, then compute sum = sum_{j=1}^{i-1} d_j * c_j + d_i * (X - prev_count). This is O(K log K) after sorting, and K ≤ N ≤ 1e5, so it's fine. But X can be up to 1e10, but that's just a number.
So we can compute f(X) in O(log N) time.
Now we need to compute the candidate X values.
Feasibility condition: X mod S ∈ R, where R = {0} ∪ [S-W, S-1] if W>0; else R = {0} (since W=0). Note that if W=0, feasible X are multiples of S only (including 0 and T). So then the condition is X ≡ 0 mod S.
We need to find:
- Largest X ≤ P-1 such that X mod S ∈ R.
- Smallest X ≥ P+Z+1 such that X mod S ∈ R.
But careful: If P = 0, then interval is [0, Z]. Then "below" P-1 is not defined (negative). So we treat separately: if P=0, then the optimal interval includes 0. So we should check feasibility of any X in [0, Z] (which includes 0). If any is feasible, answer = C (since sum positives = 0). If none, then we need to consider X > Z (since X < 0 not possible). So only candidate above: smallest X ≥ Z+1 feasible. Also maybe X=0 is included but if 0 not feasible? But if interval includes 0, and 0 might not be feasible? But 0 is a candidate; we need to check if 0 is feasible. According to condition, 0 mod S = 0, so 0 ∈ R always? 0 mod S is 0, which is in R (since R always includes 0). So 0 is always feasible! Wait check: If W>0, R includes 0. If W=0, R = {0}. So 0 is always feasible. So for P=0, 0 is always feasible, and 0 is in [0, Z] (since Z≥0). So there is always a feasible X in optimal interval. Actually if P=0 and Z=0 (all negative), optimal interval is [0,0], which includes 0. So 0 is feasible. So answer would be C (since sum positives =0). So no issue. Similarly, if P>0, the optimal interval might include values that might not be feasible; but we need to check.
Also note that T could be feasible? T may be in R? Possibly not always, but we include it in candidate above if needed.
Now, for P>0, we need to find if any X in [P, P+Z] satisfies X mod S ∈ R. Since the interval length may be up to Z (which could be large, sum of zeros count). But Z is the total number of slices with di=0. Each contestant may have di=0, and si could be up to 1e5, so Z could be huge (up to T). So we cannot iterate over all X in that interval. However, we can check existence by using the modulo condition: we need to see if there exists integer X in [L, R] with X mod S ∈ R. This is a typical problem: given a set of allowed residues modulo S (R), determine if there's an integer in interval [L,R] that is congruent to one of those residues. Since |R| = W+1 (which is ≤ S). S can be up to 1e5. So we could try each residue in R to see if the interval contains a number with that residue. But note that W+1 can be up to S, which is up to 1e5. That's okay; iterating over up to 1e5 residues is acceptable given constraints N up to 1e5 and typical time limits. But careful: In worst case, S = 1e5, W+1 could be 1e5. That's fine. So we can just for each residue r in R, compute the smallest X >= L with X ≡ r (mod S). That is: x = L + ((r - L mod S) mod S) ... standard. Then check if x <= R. If any, then optimal feasible exists. This is O(|R|) which is at most S, up to 1e5. Acceptable. However, we must also consider that T could be huge (1e10) but arithmetic is fine.
But we need to be cautious: S up to 1e5, and we have at most one test case? The problem seems single test case (no multiple testcases mentioned). So O(S) ~ 1e5 is okay.
But also we need to compute the candidate below and above if needed. For the below candidate: largest X ≤ P-1 with mod ∈ R. This can be computed by iterating over residues? We can also compute directly using arithmetic: For a given residue r, the largest number ≤ P-1 with that residue is: let x = P-1 - ((P-1 - r) mod S). Actually we can compute: x = r + S * floor((P-1 - r)/S). But we can just for each r compute that x and take the maximum among those that are ≤ P-1. Since |R| ≤ 1e5, that's okay. Similarly for above candidate: smallest X ≥ P+Z+1 with mod ∈ R: for each r, compute smallest >= L2: x = r + S * ceil((L2 - r)/S). Or using formula: x = L2 + ((r - L2) mod S). Then take the minimum among those.
Thus we can compute two candidate X values (if they exist) and compute f for them, then also consider X=0 and X=T maybe? But those might be captured: For below candidate, if P-1 is negative, we don't consider; for above candidate, L2 may be > T, then no candidate. But we should also consider X=T if it's feasible, but if we are looking for min X >= L2, and L2 could be <= T. If L2 > T, then no candidate above. But note that T itself may be feasible, but if our interval optimal is [P, P+Z] and we are looking above, L2 = P+Z+1. If P+Z = T, then L2 = T+1 > T, so no candidate above. But also maybe T is in optimal interval if T ≤ P+Z? That would be if T ≤ P+Z, but T is total slices, which is >= P+Z? Actually P+Z is count of non-negative di, which could be less than T if there are negative di. So it's possible that T is larger. If L2 ≤ T, we consider above. If L2 > T, then no above candidate.
Also, we might consider X=0 separately? But if P>0, then 0 is below P, and our below candidate will include the largest feasible ≤ P-1, which could be 0 if 0 is feasible and is the largest. So it's covered.
Similarly X=T may be covered as candidate above if it is feasible and is the smallest >= L2.
Thus algorithm:
- Read N, S.
- Compute total slices T = sum si.
- Compute M = ceil(T / S) = (T + S - 1) // S.
- Compute W = M*S - T.
- Compute di = ai - bi for each contestant.
- Build list of pairs (di, si). Note: di can be negative, zero, positive.
- Sort this list by di descending.
- Compute prefix sums of counts and values for groups.
Also compute C = sum_i si * bi.
Now compute:
P = total count of slices with di > 0. Z = total count of slices with di == 0.
Set L_opt = P, R_opt = P+Z.
Now we need to determine if there exists feasible X in [L_opt, R_opt].
Define R_set residues: if W == 0: R = {0} else: R = {0} ∪ {r | S-W <= r <= S-1}. But note that 0 may already be included in the range if S-W == 0? Since S-W >= 1 when W < S. So distinct.
We can create a list residues = [0] + list(range(S-W, S)) if W>0 else [0]. Ensure no duplicates: when W = S? But W < S, so S-W >=1, so 0 not in that range. So okay.
Now check existence:
For each r in residues:
- Compute the smallest X >= L_opt such that X ≡ r (mod S). That's: x = L_opt + ((r - L_opt) % S). Note: In Python, (r - L_opt) % S gives the needed increment.
- If x <= R_opt: then feasible exists. Break.
If found: answer = C + sum_{di>0} di (which is sum of all positive di). Compute sum_positive = sum of di over all slices with di>0. This can be computed from the grouped data: iterate over groups and sum di*count for di>0.
Else: we need to compute candidate X values.
Candidate1: largest feasible X ≤ L_opt - 1 (if L_opt >= 1). We'll compute max_feasible_below = -1 initially. For each r in residues:
- Compute the largest x ≤ L_opt - 1 with x ≡ r (mod S). That is: if L_opt - 1 < r then maybe none? Actually we can compute: floor((L_opt-1 - r)/S). If L_opt-1 >= r, then x = r + S * ((L_opt-1 - r) // S). If L_opt-1 < r, then no such x (since smallest with that residue is r > L_opt-1). So condition: x = r + S * ((L_opt-1 - r) // S) if L_opt-1 >= r. Then if x >=0, update max. But also if L_opt-1 >= 0. Since L_opt = P could be 0, then L_opt-1 = -1, no candidate. So handle.
Candidate2: smallest feasible X ≥ R_opt + 1 (if R_opt+1 ≤ T). Let L2 = R_opt + 1. For each r in residues:
- Compute smallest x ≥ L2 with x ≡ r (mod S): x = L2 + ((r - L2) % S). If x <= T, then update min_feasible_above = min(min_feasible_above, x).
We may also consider X = 0 and X = T if they haven't been covered? But they will be considered: For candidate1, if 0 is feasible and ≤ L_opt-1, then it's considered. However if L_opt = 0, then candidate1 doesn't exist; but then optimal interval includes 0 and we already checked and didn't find feasible (but we earlier argued if L_opt=0, 0 is in interval and feasible, so we would have found existence. So candidate1 only needed when L_opt>0 and no feasible in [L_opt,R_opt]. So L_opt>0, so L_opt-1 ≥0. Then candidate1 includes 0 if 0 is feasible and is the largest <= L_opt-1? But if there are other feasible numbers >0, they would be larger. So it's fine.
For candidate2, T is feasible? Possibly. It will be considered if L2 <= T and T ≡ something in R. T mod S =? T = M*S - W. So T mod S = (-W) mod S = (S - W) mod S, which if W>0 gives remainder S-W, which is in R (since R includes S-W). If W=0, T mod S = 0, also in R. So T is always feasible? Let's check: For W>0, remainder = S-W, which is in R (since R includes S-W to S-1). For W=0, remainder = 0 in R. So yes, T is always feasible. So candidate2 will include T if L2 <= T. Since T is feasible, the smallest feasible ≥ L2 could be less than or equal to T. So T will be considered implicitly as one of the residues? Possibly the min x might be T if T is the first after L2. But we need to compute min across residues.
Now after we have candidate X values (maybe one or two), compute f(X) for each, and total = C + f(X). Choose maximum.
But we also need to consider that if there are no feasible X below (i.e., max_feasible_below remains -1) and none above, then maybe only the interval itself? But we already determined interval not feasible, so must have at least one candidate? There should always be at least one feasible X overall, since the problem always has a solution. For example, X=0 always feasible. So if L_opt>0, candidate1 exists because 0 is feasible and ≤ L_opt-1 (if L_opt>0, then 0 ≤ L_opt-1 if L_opt>=1). So candidate1 will always have at least 0. So at least one candidate.
Now, the algorithm seems straightforward. Complexity: O(N log N + S) which is up to 1e5 + 1e5 = fine.
But we must also consider that W+1 could be up to S (1e5). However, S itself is at most 1e5, so it's okay.
Edge Cases:
-
S=1: Then each pizza has 1 slice. M = T, W = 0? Since T = M*1, M = T exactly, W=0. Feasible X: X mod 1 ∈ {0} -> all X feasible because any integer mod 1 = 0. So all X from 0 to T feasible. So condition simplifies. Our residues set will be {0} only, and for any X we have X mod 1 = 0, so all X feasible. Then existence check for [L_opt,R_opt] will find a feasible X (since any interval non-empty). So answer = sum positives + C. That matches expectation.
-
S > T? Then M = 1 (since ceil(T/S)=1 if T ≤ S? Actually if T <= S, then M = 1). W = S - T. So W could be positive. Then residues: R = {0} ∪ [S-W, S-1] = {0} ∪ [T, S-1]? Since S-W = S-(S-T) = T. So residues: 0 and T, T+1,..., S-1. But note X ranges from 0 to T. So feasible X are those with remainder 0 or remainder >= T. Since remainder >= T and <= S-1, but X <= T, so remainder >= T implies either X = 0? Actually if X <= T, remainder = X if X < S (since S > T). So remainder >= T implies X >= T, and also X <= T => X = T. So feasible X are 0 and T. So indeed, with one pizza, we can either have all type1 (X=T) or all type2 (X=0). So our residues approach yields that.
Now we need to handle large T but small S and N. The sorting and prefix sums can handle.
Now confirm with examples.
Example 1: N=3, S=12 si:3,4,5 => T=12, M=1, W=0, residues={0} L_opt = P: Compute di: (5-7=-2) => -2, (6-7=-1) => -1, (9-5=4) => 4. So di: -2 (3 slices), -1 (4 slices), 4 (5 slices). So positives: count =5 (since 45? Actually di=4 for contestant 3 with s=5, so 5 slices positive). Z=0. So L_opt=R_opt=5. Check if exists X=5 with X mod 12 ∈ {0}: 5 mod 12 =5 not 0. So not feasible. Now candidate1: largest feasible ≤ 4. Feasible numbers are multiples of 12 ≤4? Only 0. So max_feasible_below=0. Candidate2: smallest feasible ≥6 (since R_opt+1=6). Feasible numbers are multiples of 12 ≥6: 12. So min_feasible_above=12 (≤ T=12). So candidates: X=0 and X=12. f(0)=0, f(12)= sum of top 12 di = sum of all di = 54 + 4*(-1) + 3*(-2) =20 -4 -6=10. So total happiness = C + f(12). C = sum sibi = 37 + 47 + 55 =21+28+25=74. So total = 74+10=84. f(0)=0 => total=74. So max=84, matches output.
Example 2: N=6, S=10 Compute si, ai, bi: 1: 7 4 7 -> di=-3? Actually 4-7=-3, s=7 2: 5 8 8 -> di=0, s=5 3: 12 5 8 -> di=-3, s=12 4: 6 11 6 -> di=5, s=6 5: 3 3 7 -> di=-4, s=3 6: 5 9 6 -> di=3, s=5 Total T = 7+5+12+6+3+5 = 38? Let's compute: 7+5=12, +12=24, +6=30, +3=33, +5=38. So T=38. S=10, M = ceil(38/10)=4, W = 4*10-38=2. Residues: R = {0} ∪ [S-W, S-1] = {0} ∪ [8,9] = {0,8,9}.
Now compute di groups: Contestant 1: di=-3, count=7 2: di=0, count=5 3: di=-3, count=12 4: di=5, count=6 5: di=-4, count=3 6: di=3, count=5
Positive di: di=5 (6 slices), di=3 (5 slices) => total positive count = 11. Zero di: di=0 (5 slices). So L_opt=11, R_opt=16.
Now check existence of feasible X in [11,16] with mod 10 in {0,8,9}. Compute for each residue: r=0: smallest X>=11 with X%10=0 is 20. >16, no. r=8: smallest X>=11 with X%10=8 is 18? Actually 8,18,28... 8<11, next 18>16. So 18 >16, no. r=9: smallest X>=11 with X%10=9 is 19? Actually 9,19,... 9<11, 19>16. So none. So no feasible in interval.
Candidate1: largest feasible ≤ L_opt-1 =10. Compute for residues: r=0: largest ≤10 with %10=0 is 10 (since 0,10). So x=10. r=8: largest ≤10 with %10=8 is 8. r=9: largest ≤10 with %10=9 is 9. Take max = 10. Candidate2: smallest feasible ≥ R_opt+1 =17. Compute: r=0: smallest ≥17 with %10=0 is 20. r=8: smallest ≥17 with %10=8 is 18. r=9: smallest ≥17 with %10=9 is 19. Take min = 18? Actually 18 < 20, 18 is from r=8? Check: 18%10=8, yes. Also 19 is 9. So min is 18. But also T=38 is feasible, but 18 is smaller. So candidate2=18.
Now compute f(10) and f(18). Need sorted di descending.
Let's list all slices di values:
- di=5: 6 slices
- di=3: 5 slices
- di=0: 5 slices
- di=-3: 7+12=19 slices? Actually -3: contestant1 7, contestant3 12 => total 19 slices
- di=-4: 3 slices
Total = 6+5+5+19+3 = 38, matches.
Sorted descending: 5 (6), 3 (5), 0 (5), -3 (19), -4 (3).
Compute f(10): sum top 10 slices: includes all 6 of 5, and 4 of 3 => 65 + 43 = 30+12=42. f(18): sum top 18: includes 6 of 5, 5 of 3, 5 of 0, and 2 of -3? Wait 6+5+5=16, need 2 more from -3: so sum = 65 + 53 + 50 + 2(-3) = 30+15+0-6=39. Now C = sum sibi: compute: 1:77=49 2:58=40 3:128=96 4:66=36 5:37=21 6:5*6=30 Total = 49+40=89, +96=185, +36=221, +21=242, +30=272? Actually 221+21=242, +30=272. Wait re-calc: 185? Let's do stepwise: 49+40=89; 89+96=185; 185+36=221; 221+21=242; 242+30=272. So C=272.
Then total happiness candidates: X=10: 272+42=314. X=18: 272+39=311. So max=314, matches example output. Good.
So algorithm works.
Now we need to consider performance for large T. We need to compute P and Z (counts of positive and zero slices) from the groups. Since we have groups, we can sum counts with di > 0 and di == 0.
Also compute sum_positive = sum_{di>0} di * count.
Now one nuance: In the existence check, we used residues list of size up to S (1e5). That's okay. However, we also need to compute candidate below and above, each iterating over residues again (same list). That's 3 * |R|, still okay.
But note: In the worst case, S could be 1e5, W could be S-1, so |R| = S = 1e5. That's fine.
Now we also need to be careful about the case where the optimal interval may include X that are not feasible, but we might find a feasible X that yields the same maximum f even if not in the interval? That would mean f(X) = sum_positives for X outside [P, P+Z]. That could happen if there are zeros? If we include some negatives that cancel out? But since negatives are strictly negative, including any negative reduces sum, so can't achieve sum_positives. So only X in that interval achieve maximum. So if interval contains no feasible X, then the best feasible will be strictly less than sum_positives.
Thus our method stands.
Edge Cases to consider:
-
When P=0, we already determined existence check: interval is [0, Z]. Since 0 is always feasible, existence holds, so answer = C (since sum_positives = 0). But wait: if Z=0 and P=0 (all negative), interval is [0,0], 0 feasible, answer = C. That makes sense: best is no type1 slices, all type2, happiness = sum si * bi = C.
-
When P>0 but Z maybe huge, interval length could be large, but we check existence via residues; that's O(|R|) not dependent on interval length.
-
When P>0 and no feasible in interval, we compute candidates. Need to ensure candidate X values are within [0,T]. For candidate1, L_opt-1 could be up to T-1, but we compute largest feasible ≤ L_opt-1; it will be >=0 because 0 is always feasible. So candidate1 exists. For candidate2, we compute smallest feasible ≥ R_opt+1. It's possible that R_opt = T (if all slices are non-negative). Then R_opt+1 = T+1 > T, so candidate2 does not exist. In that case, we only consider candidate1. But note: If R_opt = T and interval not feasible, then candidate1 exists (since L_opt > 0 likely). But is it possible that R_opt = T and interval not feasible? T is always feasible as argued, and if R_opt = T, then T is in the interval, so interval would contain feasible X (since T in [L_opt,R_opt]). So that cannot happen. Because if R_opt = T, then T is in interval, and T is feasible, so existence check would have found. So candidate2 will exist only if R_opt < T, which is the case when there are negative slices. So candidate2 will exist.
-
Also need to consider when L_opt=0 but we already covered.
Now we also need to be careful about large integer arithmetic: T up to 1e10, M up to 1e10, but we only use them in arithmetic; it's fine.
Now we should also confirm that the condition for feasibility using residues is correct for X=0 and X=T. Yes.
Implementation steps:
- Read N, S.
- Initialize T=0, list of (di, si) pairs.
- Also compute C = sum_i si * bi.
- For each contestant: compute s_i, a_i, b_i. di = a_i - b_i. Append (di, s_i). T += s_i.
- Compute M = (T + S - 1) // S.
- W = M * S - T.
- Build residues list:
- residues = [0]
- if W > 0: add all r in range(S - W, S) (note: this range is inclusive of S-W to S-1). For S-W = S-W, S-1 inclusive. So for r in range(S-W, S): residues.append(r). Use a set? But we can just store list; duplicates not an issue if we ensure 0 not in that range (since S-W >=1). So we can simply residues = [0] + list(range(S-W, S)) if W>0 else [0].
But note: if W=0, then residues = [0] only.
-
Sort the di,si pairs by di descending. This yields groups.
-
Compute prefix sums? Actually we only need to compute f(X) for a few X. We can implement a function get_top_sum(X) that returns sum of largest X di values.
We can preprocess:
- Create arrays of cumulative counts and cumulative sums.
Specifically:
Let groups = sorted list of (di, count_i) in descending order.
Let cum_cnt = list of cumulative counts after each group: cum_cnt[0] = count_0, cum_cnt[1] = count_0+count_1, etc.
Let cum_sum = list of cumulative sum of dicount: cum_sum[0] = di0count0, cum_sum[1] = previous + di1*count1, etc.
Then for X, binary search for first cum_cnt >= X. Use bisect_left on cum_cnt. Then index = that position. prev_cnt = cum_cnt[index-1] if index>0 else 0. prev_sum = cum_sum[index-1] if index>0 else 0. Then extra = (X - prev_cnt) * groups[index].di. Return prev_sum + extra.
Also compute P = sum of counts for di>0. We can compute while iterating groups.
Also compute sum_positive = sum of di*count for di>0.
Also compute Z = sum of counts for di==0.
Also note: In building groups, di may be negative; we include all.
-
Determine L_opt = P, R_opt = P+Z.
-
Check feasibility in interval:
Define function is_feasible_in_interval(L,R): for each r in residues: x = L + ((r - L) % S) if x <= R: return True Return False.
If True: answer = C + sum_positive. Print answer.
Else:
Compute candidate_below = -1 if L_opt >= 1: low = L_opt - 1 for r in residues: if r > low: continue x = r + S * ((low - r) // S) # integer division if x >= 0: candidate_below = max(candidate_below, x)
Compute candidate_above = None (or large) high = T L2 = R_opt + 1 if L2 <= T: for r in residues: # smallest x >= L2 with residue r x = L2 + ((r - L2) % S) if x <= T: if candidate_above is None or x < candidate_above: candidate_above = x
Now we have candidates: candidate_below (which should be at least 0) and candidate_above (maybe None). Compute f for each, compute total = C + f(candidate). Take max. (Note: candidate_below is guaranteed to be set because at least 0 is feasible and ≤ low if low>=0. Since low = L_opt-1 >=0, and 0 <= low because L_opt >=1 => low >=0, so candidate_below will include 0 at least.)
But we must ensure that candidate_below is indeed feasible; our calculation yields x that is congruent to r mod S and ≤ low, so it's feasible.
Edge case: if L_opt = 0? Then we would have already found feasible because interval includes 0. So we don't go to else. So candidate_below only computed when L_opt>=1.
Now answer is max_total.
Now test with some custom cases.
Case: N=1, S=5, s=3, a=10, b=1 => di=9. T=3, M=ceil(3/5)=1, W=2. residues: {0} ∪ [5-2=3,4] = {0,3,4}. L_opt = P=3 (since all positive), Z=0 => interval [3,3]. Check feasible: need X=3 mod5 ∈ {0,3,4} -> 3∈{3}, so feasible. So answer = C + sum_positive = 31 + 39 = 3+27=30? Actually C= sb = 31=3; sum_positive = 39=27; total=30. But also we could order 1 pizza type1: happiness 310=30; type2:3*1=3. So correct.
Case: N=1, S=5, s=3, a=1, b=10 => di=-9. T=3, M=1, W=2, residues {0,3,4}. L_opt = P=0, Z=0? di negative => P=0, Z=0 (no zeros). interval [0,0]. 0 is feasible. answer = C = 310=30 (all type2). Could we do type1? That would be 31=3, less. So 30 optimal. Good.
Case: Mixed zeros: N=1, S=5, s=3, a=5, b=5 => di=0. T=3, M=1, W=2, residues {0,3,4}. L_opt = P=0, Z=3 => interval [0,3]. Check feasible: any X in [0,3] with mod5 in {0,3,4}. X=0 (0) feasible; X=1 mod5=1 not allowed; X=2 mod5=2 not allowed; X=3 mod5=3 allowed. So feasible exists (e.g., X=0). So answer = C + sum_positive = C + 0 = 35=15. Actually any allocation yields happiness 35=15 regardless of type, so correct.
Now case where interval not feasible but candidate above gives higher than below? Example 2 gave below better (10 vs 18). Could be opposite if positives are small? Let's test a scenario.
Suppose S=10, T=20, M=2, W=0? Actually T=20, S=10 => M=2, W=0, residues {0}. So feasible X are multiples of 10: 0,10,20. Suppose di's: positive ones sum high? But need to create case where optimal X=15 (P= some, Z maybe 0) but not feasible, then candidate below =10, above=20. Which gives higher f? Depending on marginal values. In our algorithm we compute both and compare.
Now we must handle possible overflow? Use Python ints, fine.
Now consider complexity of building residues list: For W>0, range(S-W, S) could be up to 1e5 elements. That's acceptable. However, we might have to sort groups of up to N=1e5, also fine.
Now consider memory: groups list of length up to N.
Now we need to compute sum_positive accurately: iterate through groups with di>0.
Now we need to also consider the possibility that the optimal interval [P, P+Z] might be empty if P+Z < P? No.
Now one more nuance: When checking existence in [L_opt,R_opt], we used residues list. But what if the interval length is huge and the residues set is small? Our method iterates over residues, which is at most S, fine. However, we must ensure that the computation of x for each residue uses modular arithmetic that works for large L_opt.
Now we need to also check that we correctly treat X=0 and X=T as feasible. In our candidate generation, we used residues list which includes 0. So X=0 will be considered for candidate_below if L_opt-1>=0. Good. For candidate_above, T is considered if residue matches and x = T is found.
Now we need to double-check that T is always feasible. For W>0, T mod S = (M*S - W) mod S = (-W) mod S = S-W, which is in residues because residues include S-W through S-1. So yes. For W=0, T mod S =0, also in residues. So T feasible.
Thus, candidate_above will always have at least one x (T) if L2 <= T? Not necessarily, if L2 <= T, then we compute for each residue; for residue = S-W (or 0) we can get x = L2 + ((r - L2) % S). Could this skip T? If T is greater than L2, it's possible that the smallest x with that residue >= L2 might be something less than T, like 18 in example. So T will be considered if no smaller feasible exists. But if L2 is large, maybe the smallest feasible above is some number less than T, but T is also feasible, but it's larger than that, so the min will be the smallest, which may be less than T. That's fine, because for X > R_opt, f is decreasing, so the smallest X gives highest f among those greater than R_opt. So we should take the smallest feasible X >= L2, as we planned. Because for X > R_opt, f is non-increasing as X increases (since we start adding negative values). Actually is it always non-increasing after R_opt? R_opt = P+Z. For X > P+Z, we start including negatives, so each additional slice reduces f, so f is strictly decreasing if there is at least one negative. If there are no negatives (i.e., all slices are non-negative, meaning P+Z = T), then there is no region above R_opt because R_opt = T. So we only have region below. So in region above, f is decreasing with X. Therefore, the best among X >= L2 is the smallest X (closest to R_opt). So we indeed want the minimum feasible X >= L2.
Similarly, for X < L_opt, f is increasing with X (since we are adding positive slices as X increases). So the best among X <= L_opt-1 is the largest X (closest to L_opt). So our candidate selection is correct.
Now we must be careful about the case where there are zeros and no negatives: then R_opt = T, and f is constant on [P, T] (since adding zeros doesn't change sum, and there are no negatives). Actually if there are no negatives, then all slices are non-negative (positive or zero). Then f(X) increases up to P, then constant from P to T. So the maximum is attained for any X in [P, T]. Then the optimal interval is actually [P, T]? Wait our earlier definition of optimal interval as [P, P+Z] assumed that after P+Z we have negatives, but if there are no negatives, then Z = T - P, because all non-positive? Actually zeros count Z = T - P if no negatives. Then P+Z = T. So the interval [P, P+Z] = [P, T]. So that's correct. So if there are no negatives, the optimal interval extends to T. In that case, existence check: does any X in [P, T] satisfy residue condition? If not, we go to candidate below (since above doesn't exist). Then candidate below is largest feasible ≤ P-1. Since f is increasing up to P, the best feasible below is the largest below P. That's fine.
Now we need to handle the case where P > 0 but there are no negatives and also no zeros? Then all slices positive, T = P. Then optimal interval is [P, P] (single point). That's fine.
Now, we should also consider scenario where the interval [P, P+Z] may contain multiple feasible X but we only need existence. Our method using residues works.
Potential Pitfalls:
-
Overflow in Python? Not an issue.
-
The residues list may be large; but we can store as a list and iterate.
-
Need to compute modular arithmetic correctly for negative numbers? In Python, (r - L) % S yields a non-negative remainder. It's fine.
-
For candidate below: compute x = r + S * ((low - r) // S). Ensure integer division floor. For low >= r, this works. If low < r, no such x. We can simply check if low >= r.
-
We should ensure that candidate_below is at least 0. Since low >= 0, r >=0, and if low >= r, x = r + S*((low-r)//S) will be >= r >=0. So fine.
Now, before coding, verify with additional tests.
Let's generate random small cases and brute-force to verify algorithm. We'll implement a brute-force for small N, S, small si (like up to 5) and compare.
But before coding, consider any alternative interpretation: Could we order more pizzas than the minimum? The problem says "we want to buy the minimum possible number of pizzas for all of the contestants to be able to eat their required number of slices." This implies we are constrained to use exactly that minimum number. Yes.
Now, any nuance about ordering both types? We can order any combination of types that totals M pizzas. So our constraint is correct.
Now, think about if there is any other constraint like each pizza is homogeneous type, but slices from different pizzas can be mixed per contestant arbitrarily. Yes.
Now we need to ensure we compute sum_positive correctly. But careful: f(X) = sum of top X di. If we compute sum_positive as sum of all di where di>0, that's correct only if we take all positive slices. But note that if there are positive di values, they are all taken when X >= P. So sum_positive is indeed f(P) = f(P+Z) = sum of all positive di. So answer when feasible is C + sum_positive.
Now, there is also possibility that the maximum f(X) could be higher than sum_positive if we include some negative but also some extra positive? No, because sum_positive is sum of all positives; any X < P misses some positive, any X > P includes negatives that subtract. So sum_positive is max.
Thus algorithm stands.
Now let's consider a scenario where di values are not all distinct; but grouping handles.
Now let's think about computational details: We'll have to compute the sorted groups. Since N up to 1e5, sorting by di descending is O(N log N). We'll also compute cumulative counts and sums.
Now, we need to compute P and Z; we can do that while building groups.
Implementation steps in code:
def solve(): import sys input = sys.stdin.readline N, S = map(int, input().split()) T = 0 C = 0 items = [] # list of (di, si) for _ in range(N): s, a, b = map(int, input().split()) T += s C += s * b di = a - b items.append((di, s)) M = (T + S - 1) // S W = M * S - T
# residues residues = [0] if W > 0: residues.extend(range(S - W, S)) # Note: Possibly duplicates if S-W == 0, but W>0 ensures S-W >=1, so fine. # sort items by di descending items.sort(key=lambda x: -x[0]) # compress? We'll keep as is, but need cumulative. K = len(items) d_vals = [it[0] for it in items] cnts = [it[1] for it in items] cum_cnt = [] cum_sum = [] cur_cnt = 0 cur_sum = 0 P = 0 sum_pos = 0 Z = 0 for di, cnt in items: cur_cnt += cnt cur_sum += di * cnt cum_cnt.append(cur_cnt) cum_sum.append(cur_sum) if di > 0: P += cnt sum_pos += di * cnt elif di == 0: Z += cnt # Now define function to compute f(X) def top_sum(X): # X integer 0..T if X == 0: return 0 # binary search on cum_cnt import bisect idx = bisect.bisect_left(cum_cnt, X) prev_cnt = cum_cnt[idx-1] if idx > 0 else 0 prev_sum = cum_sum[idx-1] if idx > 0 else 0 di = d_vals[idx] extra = (X - prev_cnt) * di return prev_sum + extra L_opt = P R_opt = P + Z # Check feasibility in [L_opt, R_opt] feasible_interval = False for r in residues: # smallest X >= L_opt with residue r x = L_opt + ((r - L_opt) % S) if x <= R_opt: feasible_interval = True break if feasible_interval: ans = C + sum_pos print(ans) return # Else, compute candidates best = -10**30 # or None # Candidate below if L_opt >= 1: low = L_opt - 1 max_below = -1 for r in residues: if r > low: continue x = r + S * ((low - r) // S) # x is feasible and <= low if x > max_below: max_below = x if max_below >= 0: val = C + top_sum(max_below) if val > best: best = val # Candidate above L2 = R_opt + 1 if L2 <= T: min_above = None for r in residues: x = L2 + ((r - L2) % S) if x <= T: if min_above is None or x < min_above: min_above = x if min_above is not None: val = C + top_sum(min_above) if val > best: best = val # In case both candidates not set? Should not happen. # but safe: print(best)Now test with given examples.
We'll also test with some random small cases by brute force.
But before that, we need to be careful: In the candidate above, we compute min_above as the smallest feasible X >= L2. However, if there is a feasible X exactly at L2? That would be captured.
Now, in the existence check, we considered residues list. However, note that residues list includes all residues that are feasible. But is it possible that for some X, the condition is X mod S ∈ R, but R may also include residues that are not exactly as defined? Our derivation gave R = {0} ∪ [S-W, S-1] (if W>0). But we must double-check: earlier we concluded that feasible X are those with X mod S = 0 or X mod S ≥ S-W. However, recall the derivation: X feasible iff ∃ integer p such that X ≤ pS ≤ X+W. For X with remainder r (0 ≤ r < S). The condition that there exists pS between X and X+W means either pS = X if r=0, or pS = X + (S - r) if r>0, and we need S - r ≤ W, i.e., r ≥ S - W. So indeed condition: r = 0 or r ≥ S - W. So residues set is correct.
Thus the implementation is consistent.
Now we need to verify with some borderline cases:
Case: S=2, T=3 -> M=2 (since ceil(3/2)=2), W=4-3=1. residues = {0} ∪ [2-1=1,1] = {0,1}. So all residues 0 and 1, i.e., all X mod 2 are feasible? Since residues 0,1 cover all mod 2. So all X from 0 to 3 feasible. Good.
Case: S=5, T=9 -> M=2, W=10-9=1, residues = {0} ∪ [5-1=4,4] = {0,4}. So feasible X: those with remainder 0 or 4. That means X = 0,4,5? Actually remainder 0: X=0,5,10,... up to 9 => 0,5. Remainder 4: X=4,9? 9%5=4, yes. So feasible: 0,4,5,9. That seems plausible.
Now, edge case: S=1, any T. W = M*1 - T = ceil(T) - T = 0 because T integer, M=T, W=0. residues={0}. So all X have mod 1 = 0, so all X feasible. Good.
Now, consider a scenario where the interval [L_opt, R_opt] is empty? That would happen if P > P+Z, impossible. So not.
Now, test with random small.
We'll do after coding.
Potential issues:
-
In candidate below, we compute max_below by iterating residues. But we should ensure that we consider residues that yield x <= low. Our condition r > low skip. But what if low is very small, e.g., low=0? Then only residues r=0 qualifies (since r=0 <=0, others >0). x = 0 + S * ((0-0)//S) = 0. So max_below=0. That's correct. For residues list includes 0 always.
-
For candidate above, we compute x = L2 + ((r - L2) % S). This yields the smallest number >= L2 with that residue. However, note that if L2 <= r and r is a residue, then (r - L2) % S could be 0 if L2 <= r and r - L2 < S? Actually (r - L2) % S yields (r - L2) if r >= L2, else (r - L2 + S) if r < L2. But we can also compute: if L2 <= r and r <= L2 + S-1, then the smallest >= L2 with that residue might be r itself if r >= L2. But our formula works: ((r - L2) % S) is (r - L2) if r >= L2, so x = L2 + (r - L2) = r, correct. If r < L2, then ((r - L2) % S) = (r - L2 + S) = S - (L2 - r), so x = L2 + (S - (L2 - r)) = r + S, which is the next number with that residue >= L2. So it's correct.
Now, we need to ensure that we handle large values properly.
Now we need to also consider that the number of residues might be up to S, which is up to 1e5, and we do three loops each O(S). That's okay. However, if S is 1e5 and we also have N=1e5, total operations ~3e5 plus sorting ~1e5 log 1e5 = fine.
But wait: In some cases, S could be as large as 1e5, but W could be close to S, so residues list size ~1e5. That's okay.
But what about time for each loop? O(1e5) is trivial.
Now, we need to ensure that we compute top_sum efficiently for up to two X. That's O(log N).
Now, we also need to consider the case where L_opt = 0 and we go into else? Actually if L_opt=0, then existence check: interval [0, Z] includes X=0, which is feasible. So we will have feasible_interval True. So we never go to else.
Now, we also must consider the case where P>0 but L_opt = 0? Not possible because P>0 implies L_opt>0.
Now, we might need to also consider that sum_positive might be large (up to 1e5 * 1e5 * 1e5? Actually di up to 1e5, si up to 1e5, product up to 1e10, sum up to 1e15). Python int handles.
Now, check for potential off-by-one in residue intervals: For W>0, we include residues from S-W to S-1 inclusive. Confirm with derivation: condition r ≥ S-W. So if S-W = 1, residues 1,2,...,S-1. So range(S-W, S) gives integers from S-W to S-1 inclusive. Good.
Now, we need to ensure we handle the case where W=0 correctly: residues only [0]. That's fine.
Now, test with some random small.
We'll write a brute-force for small parameters: generate random N small (like 1-4), S small (like 2-5), random si small (1-3), random ai, bi (1-5). Compute answer by enumerating all possible P1 from 0 to M, and for each, X can be any integer from max(0, pS-W) to min(pS, T) (since we can choose allocation). But we also need to allocate xi to maximize happiness for given X. But brute-force can simply iterate over all X feasible (by checking condition) and compute f(X) as described (since that's optimal allocation for given X). Then take max total. That should match our algorithm.
Let's do mental test: but better to run code later.
But before finalizing, we should check for potential nuance: The allocation of slices to contestants must be integer slices per contestant. Our f(X) assumes we can allocate any X slices as type1 arbitrarily among contestants, as long as each gets at most si. That's valid because we can assign type1 slices to those with highest di. So for any X, the maximum happiness achievable is indeed C + sum of top X di. So that part is correct.
Now, is there any additional constraint that the total type1 slices used must exactly fill some number of whole pizzas? But we already accounted: we can have leftover slices in a pizza. There's no requirement that each pizza is fully consumed. So it's okay.
Thus solution is correct.
Now we need to produce final answer.
But before final code, we might consider if there is a more efficient way to compute candidate_below and candidate_above without iterating over all residues, but O(S) is fine.
Potential improvement: Since residues set is essentially a set of consecutive residues (0 and a block at the top), we could compute candidate_below and candidate_above using arithmetic formulas. For example, candidate_below = max( largest multiple of S ≤ low, largest number ≡ r in [S-W, S-1] ≤ low ). But we can compute directly: the largest feasible X ≤ low is either the largest multiple of S ≤ low, or if low >= S-W, then maybe a number with remainder in [S-W, S-1] could be larger. So we can compute in O(1). Similarly for above. But not needed.
But for completeness, we can implement O(1) formulas:
- The largest multiple of S ≤ low is low - (low % S). That is residue 0 candidate.
- For the block of residues [S-W, S-1], the largest ≤ low can be computed as: if low >= S-1, then we can take low - (low % S) + (S-1) but careful: the largest number with remainder in that range ≤ low is: let r = low % S; if r >= S-W, then low itself has a feasible residue? Actually if low's own remainder is in the block, then low is feasible. Else, the next lower number with remainder in block would be low - (r - (S-1))? Actually if r < S-W, then the largest number with remainder in block is low - r - 1? Not exactly. Let's derive: For numbers with remainder in [S-W, S-1], they are of the form qS + t where t ∈ [S-W, S-1]. Given low, let q = low // S, r = low % S. If r >= S-W, then low itself is feasible. Else, then the largest feasible is qS + (S-1) if qS + (S-1) ≤ low? But qS + (S-1) = (q+1)S -1. Since r < S-W, we have low < qS + (S-W). So (q+1)S -1 > low? Actually (q+1)S -1 = qS + S -1, which is > low because S-1 >= S-W? Since S-W ≤ S-1, and low < qS + (S-W) ≤ qS + S-1, so (q+1)S -1 > low, so not ≤ low. So we need to consider qS -1? But qS -1 has remainder S-1, but is it ≤ low? qS -1 = (q-1)S + (S-1). Since low >= qS? Actually low = qS + r, with r < S-W, so low >= qS (if r>=0). So qS -1 < qS ≤ low? Actually qS -1 < qS ≤ low (since low ≥ qS). But is qS -1 feasible? Its remainder is S-1, which is in block, and it is ≤ low because low ≥ qS > qS-1. So qS-1 is feasible and is the largest feasible less than or equal to low? Let's check: Could there be a number between qS-1 and low that is feasible? Since low = qS + r, and r < S-W, numbers between qS and low have remainders from 0 to r, which are not in block (since r < S-W). So no. Also numbers below qS-1: the next feasible might be (q-1)S + (S-1) = qS -1 as we have, or (q-1)S + (S-2) etc, but those are less than qS-1. So the largest feasible ≤ low is qS-1, provided qS-1 ≥ 0. But is qS-1 always feasible? Its remainder is S-1, which is in block as long as S-1 >= S-W => W>=1, which is true when W>0. If W=0, block is empty, only residue 0. So in W>0 case, qS-1 is feasible. But need to check if qS-1 could be negative? If q=0, then qS-1 = -1, invalid. So we must handle that.
Thus we can compute candidate_below more efficiently without iterating all residues. But simpler to just loop over residues; it's okay.
Given S up to 1e5, it's fine.
Now, confirm that we treat case W=0 correctly: residues only [0]. Then candidate below: only residue 0, so max_below is the largest multiple of S ≤ low. candidate above: only residue 0, so min_above is smallest multiple of S ≥ L2.
This matches.
Now, test edge case: Suppose S=100000, T large, W may be up to 99999, residues size = 100000. Loop 3 times = 300k iterations, which is trivial.
Now we need to be careful that in Python, iterating over range(S-W, S) when S large and W small (like W=1) yields a range of size 1; fine. When W large (like 99999) range size 99999; still fine.
Now, one more nuance: The total number of pizzas M could be huge (up to 1e10) but we never use M except to compute W. So fine.
Now, one potential oversight: The feasible set derived as X mod S ∈ R might have missed the X=0 case? Actually 0 mod S = 0 always in R, so included. And X=T also included.
Now, verify with a scenario where W=0, but L_opt might be a multiple of S? Then existence check will find x = L_opt if L_opt % S == 0. Good.
Now, check a scenario where W>0 and L_opt is such that there is a feasible X in interval but our residue iteration might miss due to not checking both 0 and block correctly? We check both.
Now, we also need to ensure that top_sum function handles X=0 correctly. We'll have early return.
Now, implement.
But before finalizing, we should test with random brute force.
We'll do a quick mental test:
Case: N=2, S=3, T: s1=2, s2=2 => T=4. M=ceil(4/3)=2, W=6-4=2. residues: {0} ∪ [3-2=1,2] = {0,1,2}. So all residues mod 3 are feasible? Since residues 0,1,2 cover all, so all X feasible.
Now di values: suppose d1=10 (s=2), d2=-5 (s=2). Then positive count P=2, Z=0, L_opt=2,R_opt=2. Check feasible: X=2 mod3=2 in residues -> feasible. So answer = C + sum_pos = C+20.
Now if di: d1=10 (s=2), d2=0 (s=2). Then P=2, Z=2, L_opt=2,R_opt=4. Any X in [2,4] feasible? Since all X feasible, yes. So answer = C+20.
Now if di: d1=10 (s=2), d2=-1 (s=2). P=2, Z=0, interval {2}. Since all X feasible, answer = C+20.
Now if di: d1=2 (s=2), d2=-10 (s=2). P=2, Z=0, interval {2} feasible. Answer.
Now a case where not all X feasible: S=3, T=5 => M=2, W=6-5=1, residues: {0} ∪ [3-1=2,2] = {0,2}. So feasible X: remainders 0 or 2. So X=0,2,3? 3%3=0,5%3=2, etc. So feasible: 0,2,3,5? Actually up to 5: 0,2,3,5. (1 and 4 are not).
Now suppose di: positive count P=3, Z=0 -> interval [3,3]. X=3 mod3=0 => feasible. So answer.
Suppose P=1, Z=0 -> interval [1,1]. X=1 not feasible. Then candidates: below largest feasible ≤0 -> 0; above smallest feasible ≥2 -> 2. So compare f(0)=0, f(1) is sum of top 1 positive, f(2) includes positive + next highest which might be negative. So pick max.
Let's test concrete: N=2, s1=1, a1=10,b1=1 => di=9; s2=4, a2=1,b2=10 => di=-9? Actually a2=1,b2=10 => di=-9. Total T=5. So P=1, Z=0. Compute f(0)=0, f(1)=9, f(2)=9+(-9)=0, f(3)=9+(-9)+(-9)=-9? Actually second contestant has 4 slices all -9. So f(2)=9 + (-9) =0; f(3)=9 + (-9) + (-9) = -9. So best among feasible: 0 and 2 both yield 0 extra? Actually f(2)=0, f(0)=0, f(1)=9 but not feasible. So best extra is 0. So total happiness = C + 0. C = 11 + 410 = 1+40=41. So total 41. If we could use X=1, total would be 41+9=50, but not possible due to pizza constraints? Let's see if we can achieve X=1 with minimal pizzas? M=2, W=1, residues {0,2}. So X must be 0,2,3,5. So we cannot have exactly 1 type1 slice. Is there a way to allocate that yields higher happiness? Could we order one type1 pizza and one type2 pizza? That gives capacity: type1 slices: S=3, type2 slices:3. To serve 1 type1 slice and 4 type2 slices, we need at least 1 type1 slice (available 3) and 4 type2 slices (available 3) but need 4 type2 slices, insufficient. So we cannot have exactly 1 type1 slice because that would require 4 type2 slices but we only have 3 from the type2 pizza. Could we order two type1 pizzas? Then type1 capacity 6, type2 capacity 0; we would have to serve 5 type1 slices, but then we would have 5 type1 slices, which yields extra = 9 + 4*(-9) = -27? Actually 5 slices type1: all slices type1: extra = 9 + 4*(-9) = -27; total happiness = 41-27=14. That's worse. Two type2 pizzas: all type2, extra 0, total 41. So best is 41, matching our candidate (0 or 2). Our algorithm would pick candidate_below=0, candidate_above=2, compute f(0)=0, f(2)=0, best total 41. So answer 41.
But could there be a scenario where f(above) is better than f(below) even though f is decreasing above? Since f decreases, the smallest above gives highest. That's what we pick.
Now test with scenario where zeros present: P=1, Z=1 (i.e., one zero slice), and negatives. Then interval [1,2]. If feasible X=1 and 2 are not both feasible? Suppose residues allow only X=0,3,... Then maybe X=2 not feasible, X=1 not feasible. So candidates below largest feasible ≤0 -> 0; above smallest feasible ≥3 -> 3. Then we compare f(0) vs f(3). f(3) includes the positive, zero, and a negative; might be less than f(0) if negative large. But our method picks both and compares.
Now, confirm with code.
Now, before coding, consider if we need to use 64-bit ints. Python int is arbitrary.
Now, edge case: S could be 100000, T could be 10000000000, M huge, but we compute W as MS - T, which could be up to S-1 (since M = ceil(T/S)). MS might overflow in languages with 32-bit, but Python fine.
Now, we should also check if we need to consider the possibility of ordering zero pizzas? M is at least 1 since T>=1. So fine.
Now, think about if there is any misinterpretation: The problem says "buy the minimum possible number of pizzas for all of the contestants to be able to eat their required number of slices." That might imply that we are allowed to buy that number (or more?) but we want to minimize number of pizzas bought, and given that we buy the minimum possible, maximize happiness. So we are forced to use exactly that minimum number. Yes.
Now, consider scenario where total slices T is multiple of S, then W=0, feasible X are multiples of S. That means we must allocate type1 slices in multiples of S (including 0 and T). So we can't have any fractional pizza; each pizza is wholly one type. That matches: if we buy M pizzas, each pizza is either type1 or type2. So total type1 slices must be integer multiple of S (since each type1 pizza contributes S slices). So indeed X must be multiple of S. That's consistent: when W=0, the intervals [pS - W, pS] degenerate to just {pS}. So feasible X are exactly multiples of S. Good.
Now, we should also confirm that our derivation using intervals yields same. So all consistent.
Now, we can implement.
Potential improvements: Precompute top_sum via prefix arrays; we'll implement as described.
Now, test with random small.
We'll produce a script later.
One more nuance: The contestants each eat exactly si slices. The allocation of type1 and type2 slices per contestant is independent; we can assign any xi between 0 and si. So yes.
Now, final answer is as above.
But I must consider if there is any scenario where the optimal X is not exactly the count of positive di due to the fact that we might be forced to waste slices, which could change the optimal allocation? Actually, waste does not affect the allocation to contestants; we can always leave leftover slices uneaten. So the only constraint is the total number of type1 slices X must be feasible. So we maximize f(X) over feasible X. So yes.
Now, think about if there is a possibility that we could achieve a higher total happiness by not using all slices? No, contestants must eat all their slices (they will eat exactly si slices). So total slices consumed is T fixed.
Now, finalize.
We'll now write the code with careful input parsing and function definitions.
Testing on examples:
Example1: output 84, Example2: 314.
Now, we need to handle large input efficiently, use sys.stdin.
Now, possible pitfalls: The list items might contain many entries with same di; we don't need to combine them, but sorting them as is and then building cumulative arrays from the list (which may have up to N=1e5 entries) is fine. However, if there are many contestants with same di, we could combine to reduce size, but not necessary.
But note: In prefix sums, we will have K = N entries. Binary search on cum_cnt is O(log N). That's fine.
Now, we must ensure that cum_cnt is a list of cumulative counts. But when we compute top_sum, we need to find idx such that cum_cnt[idx] >= X. Use bisect_left.
Implementation details:
- After sorting items by di descending, we have two lists: d_vals, cnts.
- Build cum_cnt = [] and cum_sum = []. cur = 0 for i in range(K): cur += cnts[i] cum_cnt.append(cur) cum_sum.append((cum_sum[-1] if i>0 else 0) + d_vals[i]*cnts[i])
Now, top_sum:
if X == 0: return 0 idx = bisect_left(cum_cnt, X) if idx == 0: return d_vals[0] * X else: prev_cnt = cum_cnt[idx-1] prev_sum = cum_sum[idx-1] return prev_sum + (X - prev_cnt) * d_vals[idx]
Now, we should test with a case where X equals total T: then idx will be K-1 (since cum_cnt[-1] = T). Works.
Now, compute P and sum_pos and Z. We can compute while building the sorted list or before sorting? Since we need counts for positive and zero, we can compute from original items before sorting, as di sign doesn't change with sorting. So we can compute P, Z, sum_pos from the original list. But note: if we sort later, it doesn't affect these aggregates. So we can compute first from items (unsorted) to get P, Z, sum_pos. That may be simpler: iterate through items once before sorting, compute T, C, and also accumulate P, Z, sum_pos. Sorting later only for cum arrays. That is fine. We must ensure we don't lose the original items; we have them in a list.
So we can do:
items = [] P = Z = 0 sum_pos = 0 for each input: items.append((di, si)) if di > 0: P += si; sum_pos += di*si elif di == 0: Z += si
Then after that, sort items by di descending.
Then build cum arrays from sorted items.
Now, about sum_pos: it is sum of di * si for di>0. This matches the extra from taking all positive slices.
Now, one more nuance: In the case where there are positive di but also zeros, the maximum extra happiness is sum_pos. That is correct.
Now, compute L_opt = P, R_opt = P+Z.
Now, check existence. If exists, answer = C + sum_pos.
Otherwise, compute candidates.
Now, we must also consider the possibility that P+Z may be > T? That would happen if there are no negatives, but then Z = T - P, so P+Z = T. So not > T.
Now, test with scenario: all di negative => P=0, Z=0, interval [0,0]. Since 0 feasible, answer = C. Good.
Now, we should ensure that in existence check, we consider X=0 if 0 in [L_opt,R_opt] (i.e., when L_opt=0). So feasible_interval true. So answer = C + sum_pos? But sum_pos=0, so answer = C. Correct.
Now, we also need to consider the case where L_opt > T? Not possible.
Now, check if we need to also consider the possibility that we could order pizzas such that the number of type1 slices X is not exactly an integer? No.
Now, think about potential integer division issues when computing residues for large numbers: Python's modulo works fine.
Now, ensure that we use // for integer division.
Now, we should also verify that when W > 0, residues list includes range(S-W, S). But if S-W == 0? That would happen if W = S, but W < S because W = MS - T, and T > 0, so M = ceil(T/S) => MS - T < S. So W ∈ [0, S-1]. So S-W >= 1. So fine.
Now, test with a random small case via mental but better to code and test.
Now, write code.
But before finalize, we must also consider if there is any more efficient method that doesn't require iterating over residues? But it's fine.
Now, add a note: The problem may have multiple test cases? The problem statement says "The first line of input will contain integers N and S" and then N lines. No mention of multiple test cases. So single test case.
Now, finalize code.
Let's implement.
But there is a nuance: In candidate_below, we compute x = r + S * ((low - r) // S). However, if low < r, we skip. That's fine. But we must ensure that when low is very large, the expression yields integer within bounds.
Now, for candidate_above, we compute x = L2 + ((r - L2) % S). But note that if L2 is huge, (r - L2) % S is computed using modulo, which is fine.
Now, consider the possibility that residues list is large, but we could break early if we find an x exactly at L_opt? Not needed.
Now, one more check: When checking feasibility in interval, we could also break early once found. That's fine.
Now, we should also consider that the top_sum function might be called with X=0; we handle.
Now, overall complexity: O(N log N + S).
Now, we can also consider that if S is large (1e5) and W is small, residues list small, but still fine.
Now, code.
We'll write solve() function.
Potential pitfalls: Input reading: lines after first: each with three ints. Use map.
Now, test with given examples.
Example1: N=3 S=12 lines as given. Our algorithm yields 84.
Example2 yields 314.
Now, let's test with a simple case: N=1, S=5, s=5, a=10,b=1 => di=9, T=5, M=1,W=0,residues[0], L_opt=5,R_opt=5. Check: X=5 mod5=0 feasible? 5%5=0, yes. Answer = C + sum_pos = 51 +45=5+45=50. That's same as 510=50.
Now, N=1, S=5, s=3, a=10,b=1 => di=9, T=3, M=1,W=2, residues [0,3,4]? Actually S-W=3, range 3,4 => residues 0,3,4. L_opt=3,R_opt=3. Check X=3%5=3 in residues? Yes. Answer = C+27 = 3+27=30. Works.
Now, N=1, S=5, s=3, a=1,b=10 => di=-9, L_opt=0,R_opt=0 -> feasible, answer = C = 30.
Now, test with random small by brute.
We'll simulate quickly: I'll write a short Python script mentally? but maybe trust.
I think solution is correct.
Now, final answer.
We'll output ans.
Now, consider an edge: If candidate_below yields a negative x? Not possible.
Now, I'll produce final code. ```python import sys import bisect
def solve() -> None: it = iter(sys.stdin.read().strip().split()) try: N = int(next(it)) S = int(next(it)) except StopIteration: return
T = 0 C = 0 items = [] # (di, si) P = 0 # number of slices with di > 0 Z = 0 # number of slices with di == 0 sum_pos = 0 # Σ (di * si) over di > 0 for _ in range(N): s = int(next(it)) a = int(next(it)) b = int(next(it)) T += s C += s * b di = a - b items.append((di, s)) if di > 0: P += s sum_pos += di * s elif di == 0: Z += s # minimal number of pizzas and waste M = (T + S - 1) // S W = M * S - T # set of feasible residues modulo S residues = [0] if W > 0: residues.extend(range(S - W, S)) # S-W .. S-1 # sort slices by decreasing di items.sort(key=lambda x: -x[0]) d_vals = [it[0] for it in items] cnt_vals = [it[1] for it in items] K = len(items) # build prefix arrays cum_cnt = [] cum_sum = [] cur_cnt = 0 cur_sum = 0 for i in range(K): cur_cnt += cnt_vals[i] cur_sum += d_vals[i] * cnt_vals[i] cum_cnt.append(cur_cnt) cum_sum.append(cur_sum) # function to compute f(X) = sum of largest X di def top_sum(X: int) -> int: if X == 0: return 0 idx = bisect.bisect_left(cum_cnt, X) if idx == 0: return d_vals[0] * X prev_cnt = cum_cnt[idx - 1] prev_sum = cum_sum[idx - 1] return prev_sum + (X - prev_cnt) * d_vals[idx] L_opt = P R_opt = P + Z # check whether some X in [L_opt, R_opt] is feasible feasible_in_interval = False for r in residues: x = L_opt + ((r - L_opt) % S) if x <= R_opt: feasible_in_interval = True break if feasible_in_interval: print(C + sum_pos) return # otherwise try the two closest feasible X best = -10**30 # candidate below: largest feasible X <= L_opt-1 if L_opt >= 1: low = L_opt - 1 max_below = -1 for r in residues: if r > low: continue x = r + S * ((low - r) // S) if x > max_below: max_below = x if max_below >= 0: val = C + top_sum(max_below) if val > best: best = val # candidate above: smallest feasible X >= R_opt+1 L2 = R_opt + 1 if L2 <= T: min_above = None for r in residues: x = L2 + ((r - L2) % S) if x <= T: if min_above is None or x < min_above: min_above = x if min_above is not None: val = C + top_sum(min_above) if val > best: best = val print(best)if name == "main": solve()