题目描述

餐厅里有 $N$ 个主菜和 $M$ 个副菜，第 $i$ 个主菜的价格为 $A_i$，第 $j$ 个副菜的价格是 $B_j$。餐厅现在要推出一些套餐，每个套餐均由一道主菜和一道副菜组成，对于一个由第 $i$ 个主菜和第 $j$ 个副菜组成的套餐，我们定义 $s=A_i+B_j$，那么这个套餐的价格即为 $\min (s,P)$，$P$ 为一个给定的常数。

请你求出所有可能的套餐的价格总和。

输入格式

第一行三个整数 $N,M,P$。

第二行 $N$ 个整数，表示 $A_1,A_2 \dots A_N$。

第三行 $M$ 个整数，表示 $B_1,B_2 \dots B_N$。

输出格式

一行一个整数表示答案。

2 2 7
3 5
6 1

24

1 3 2
1
1 1 1

6

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

2115597124

提示

• $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$
• 所有输入值均为整数。

Sample Explanation 1

• 如果您选择第一道主菜和第一道配菜，套餐价格为 $\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$ 。