2510 - 定价

Description

餐厅里有 $N$ 个主菜和 $M$ 个副菜，第 $i$ 个主菜的价格为 $A_i$ ，第 $j$ 个副菜的价格是 $B_j$ 。

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

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

Input

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

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

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

Output

一行一个整数表示答案。

Examples

Input

2 2 7
3 5
6 1

Output

Input

1 3 2
1
1 1 1

Output

Input

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

Output

2115597124

Hint

30%的数据： $n,m \leq 1000$

100%的数据： $n,m \leq 2 \times 10^5,k \leq 10^7$

题目参数

Time Limit	1 second
Memory Limit	128 MB
提交次数	44
通过次数	16

Discuss

Stats

上一题

下一题