题目描述

学校餐厅共有 N 种主餐和 M 种不同风味的酸奶可以搭配。第 i 种主餐的价格为 $A_i$，第 j 种风味的酸奶价格为 $B_j$。学校决定推出主餐和酸奶搭配的套餐。一种套餐包含一种主餐和一种酸奶，两者价格之和为 S。而物价局规定每个学生每一餐的总价不能超过 P，学校就把每一种套餐的价格定为 $\min(S, P)$。

显然这些搭配的套餐总共有 $N \times M$ 种，小高想知道所有的这些套餐的价格之和为多少。

输入格式

第一行三个空格隔开的正整数，分别表示 N，M， P；

第二行有 N 个空格隔开的整数，分别表示主餐的价格；

第三行有 M 个空格隔开的整数，分别表示不同风味酸奶的价格。

输出格式

一行一个数，表示所有套餐价格之和。

样例 #1

样例输入 #1

2 2 7
3 5
6 1

样例输出 #1

24

样例 #2

样例输入 #2

1 3 2
1
1 1 1

样例输出 #2

6

样例 #3

样例输入 #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

数据规模

30% 的数据

• $1\leq\ N,M\ \leq\ 2\times\ 10^3$
• $1\leq\ A_i,B_j\ \leq\ 10^3$
• $1\leq\ P\ \leq\ 2\times\ 10^3$

100%的数据

• $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$