分数: 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