Overview

The minimum (or rather, always the same) total time is simply the sum of all ingredient preparation times plus the mandatory rest time \(M \times R\).

Analysis

The key insight of this problem is that “changing the order does not change the total time.”

• Since all ingredient preparations must be performed, the total preparation time is always \(\sum_{i=1}^{N} T_i\) regardless of order.
• There are “exactly \(M\) rests” of “\(R\) seconds each,” so the total rest time is always \(M \times R\).
• Rests can only be taken “immediately after finishing an ingredient” and cannot be taken “before the first” or “after the last,” but the constraint guarantees \(M \le N-1\).
  This means that by inserting rests between ingredients (there are \(N-1\) gaps in total), we can always fit exactly \(M\) rests.

Therefore, there is no room to optimize by choosing which ingredient to do first or where to insert rests. The minimum value is always [ \sum_{i=1}^{N} T_i + M R ]

Concrete example:
When \(N=3, M=1, R=10, (T_1,T_2,T_3)=(3,100,5)\),
regardless of order, the total preparation time is \(3+100+5=108\), and there is 1 rest of \(10\).
The total is always \(118\) seconds (it remains the same no matter where the rest is placed).

A naive approach like “brute-force all orderings” or “DP over rest positions” would be far too slow since \(N\) can be up to \(2 \times 10^5\). However, based on the observation above, the computation reduces to simple addition.

Algorithm

1. Read the input.
2. Compute \(\text{ans} = \left(\sum T_i\right) + M \times R\).
3. Output \(\text{ans}\).

Complexity

• Time complexity: \(O(N)\) (just computing the sum of \(T_i\))
• Space complexity: \(O(N)\) (for storing the input array; can be reduced to \(O(1)\) by accumulating on the fly without storing)

Implementation Notes

• The answer can be as large as \(\sum T_i \le 2\times10^5 \times 10^9 = 2\times10^{14}\), and \(M R\) is added on top of that, so a \(64\)-bit integer type is required (Python’s int handles this without issue).

• Since the input can be large, using sys.stdin.buffer.read() for fast input is recommended to be safe.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M, R = data[0], data[1], data[2]
    T = data[3:3+N]
    ans = sum(T) + M * R
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.