A - 配送トラックの選択 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

高橋君は運送会社の配送計画担当者です。彼は N 台の配送トラックの中からちょうど 1 台を選び、配送業務を割り当てる必要があります。

各トラック i（ 1 \leq i \leq N ）には、燃費係数 E_i が設定されています。燃費係数が大きいトラックほど、同じ距離を走るのに多くの燃料を消費します。

配送ルートは M 個の区間から構成されており、 j 番目（ 1 \leq j \leq M ）の区間の距離は C_j です。選んだトラックはこれら M 個の区間をすべて走行します。トラック i が j 番目の区間を走行するときに消費する燃料は E_i \times C_j です。

トラック i を選んだときの燃料消費量の合計は

\displaystyle \sum_{j=1}^{M} E_i \times C_j

です。 N 台のトラックの中から燃料消費量の合計が最小となるようにちょうど 1 台を選んだときの、最小の燃料消費量を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq E_i \leq 10^4（ 1 \leq i \leq N ）
  • 1 \leq C_j \leq 10^4（ 1 \leq j \leq M ）
  • 入力はすべて整数
  • 答えは 10^{13} 以下であり、64ビット整数に収まる

入力

N M
E_1 E_2 \ldots E_N
C_1 C_2 \ldots C_M
  • 1 行目には、トラックの台数を表す整数 N と、配送ルートの区間数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各トラックの燃費係数を表す N 個の整数 E_1, E_2, \ldots, E_N が、スペース区切りで与えられる。
  • 3 行目には、各区間の距離を表す M 個の整数 C_1, C_2, \ldots, C_M が、スペース区切りで与えられる。

出力

最小の燃料消費量を 1 行で出力してください。

入力例 1

3 4
5 3 7
2 4 1 3

出力例 1

30

入力例 2

5 6
12 8 15 6 10
5 3 8 2 7 4

出力例 2

174

入力例 3

10 8
100 250 80 320 150 90 200 180 75 110
50 120 30 85 200 65 40 95

出力例 3

51375

Score : 200 pts

Problem Statement

Takahashi is a delivery planning manager at a shipping company. He needs to select exactly 1 truck out of N delivery trucks and assign it to a delivery task.

Each truck i (1 \leq i \leq N) has a fuel efficiency coefficient E_i. A truck with a larger fuel efficiency coefficient consumes more fuel to travel the same distance.

The delivery route consists of M segments, and the distance of the j-th segment (1 \leq j \leq M) is C_j. The selected truck will travel all M segments. The fuel consumed when truck i travels the j-th segment is E_i \times C_j.

The total fuel consumption when truck i is selected is

$\displaystyle \sum_{j=1}^{M} E_i \times C_j$

Find the minimum total fuel consumption when exactly 1 truck is chosen from the N trucks to minimize the total fuel consumption.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq E_i \leq 10^4 (1 \leq i \leq N)
  • 1 \leq C_j \leq 10^4 (1 \leq j \leq M)
  • All input values are integers
  • The answer is at most 10^{13} and fits in a 64-bit integer

Input

N M
E_1 E_2 \ldots E_N
C_1 C_2 \ldots C_M
  • The first line contains an integer N representing the number of trucks and an integer M representing the number of segments in the delivery route, separated by a space.
  • The second line contains N integers E_1, E_2, \ldots, E_N representing the fuel efficiency coefficients of each truck, separated by spaces.
  • The third line contains M integers C_1, C_2, \ldots, C_M representing the distance of each segment, separated by spaces.

Output

Print the minimum fuel consumption on a single line.

Sample Input 1

3 4
5 3 7
2 4 1 3

Sample Output 1

30

Sample Input 2

5 6
12 8 15 6 10
5 3 8 2 7 4

Sample Output 2

174

Sample Input 3

10 8
100 250 80 320 150 90 200 180 75 110
50 120 30 85 200 65 40 95

Sample Output 3

51375