← 返回题目列表

AtCoder · abc321_d

G. 设置菜单

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

分数: 400 点

问题陈述

AtCoder食堂优惠 N 主菜和 M 配菜。的价格 i-第一个主菜是 A_i,以及 j第一个配菜是 B_j。 食堂正在考虑推出新的套餐菜单。 一份套餐由一份主菜和一份配菜组成。让 s 为主菜和配菜的价格之和,则套餐的价格为 \min(s,P)。 在这里, P 是输入中给出的常数。

有 NM 套餐主菜和配菜的选择方法。求所有这些套餐的总价。

约束

  • 1\leq N,M \leq 2\times 10^5
  • 1\leq A_i,B_j \leq 10^8
  • 1\leq P \leq 2\times 10^8
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M P
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M

输出

将答案打印为整数。 在该问题的约束下,可以证明答案符合 64- 位有符号整数。


示例输入 1

2 2 7
3 5
6 1

示例输出 1

24
  • 如果选择第一道主菜和第一道配菜,则套餐价格为 \min(3+6,7)=7.
  • 如果您选择第一道主菜和第二道配菜,则套餐价格为 \min(3+1,7)=4.
  • 如果选择第二个主菜和第一道配菜,则套餐价格为 \min(5+6,7)=7.
  • 如果选择第二个主菜和第二个配菜,则套餐价格为 \min(5+1,7)=6.

因此,答案是 7+4+7+6=24.


示例输入 2

1 3 2
1
1 1 1

示例输出 2

6

示例输入 3

7 12 25514963
2436426 24979445 61648772 23690081 33933447 76190629 62703497
11047202 71407775 28894325 31963982 22804784 50968417 30302156 82631932 61735902 80895728 23078537 7723857

示例输出 3

2115597124