← 返回题目列表

AtCoder · awc0007_a

A. 送货卡车的选择

中文机器翻译题面 查看原题

分数: 200 分

问题陈述

Takahashi 是一家航运公司的配送计划经理。他需要准确选择 1 卡车驶出 N 送货卡车并将其分配给送货任务。

每辆卡车 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$

找出恰好时的最小总油耗 1 卡车选自 N 卡车尽量减少总油耗。

约束

  • 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
  • 第一行包含一个整数 N 代表卡车数量和一个整数 M 表示配送路线中的段数,以空格分隔。
  • 第二行包含 N 整数 E_1, E_2, \ldots, E_N 代表每辆卡车的燃油效率系数,以空格分隔。
  • 第三行包含 M 整数 C_1, C_2, \ldots, C_M 代表每段的距离,以空格分隔。

输出

在一行上打印最低油耗。


示例输入 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