Overview

Given the fuel efficiency coefficients \(E_i\) for each truck and the distances \(C_j\) to all delivery destinations, the problem is to minimize the total fuel consumption \(E_i \times \sum C_j\) when a single truck visits all delivery destinations.

Analysis

The fuel for truck \(i\) to go to delivery destination \(j\) is \(E_i \times C_j\), so the total fuel to visit all delivery destinations is

[ \sum_{j=1}^{M} (E_i \times C_j) = Ei \times \sum{j=1}^{M} C_j ]

The key observation here is that \(\sum C_j\) is the same regardless of which truck is chosen. In other words, the only part of the total fuel that varies by truck is \(E_i\), so:

• \(\sum C_j\) is fixed
• Therefore, to minimize the total fuel, we only need to minimize \(E_i\)

Problem with the Naive Approach

For example, if we “compute the fuel for each truck across all \(M\) delivery destinations, sum them up, and find the minimum,” the computational complexity would be \(O(NM)\).
Since \(N, M \le 10^5\), this results in roughly \(10^{10}\) operations in the worst case, which will not finish in time (TLE).

Solution

From the formula transformation above, all we need is:

• The minimum of \(E_i\): \(\min(E)\)
• The sum of distances: \(\sum C\)

And the answer is

[ \min(E) \times \sum C ]

(Example) When \(E=[3,5,2]\), \(C=[4,1,6]\):
\(\sum C=11\), \(\min(E)=2\), so the answer is \(2 \times 11 = 22\).

Algorithm

1. Find the minimum value of array \(E\): \(e_{\min} = \min(E)\)
2. Find the total sum of array \(C\): \(s = \sum C\)
3. Output \(e_{\min} \times s\) as the answer

Complexity

• Time complexity: \(O(N + M)\) (one pass each for the minimum value and the sum)
• Space complexity: \(O(N + M)\) (to store the input arrays; this can be reduced to \(O(1)\) with careful input reading)

Implementation Notes

• The answer can be as large as \(10^4 \times (10^5 \times 10^4) = 10^{13}\), but since Python’s int supports arbitrary precision, there is no concern about overflow.

• Since the input can be large, reading it all at once with sys.stdin.buffer.read() is faster.

  Source Code

import sys

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

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.