题目描述

$Bob$ 去餐厅实习，餐厅经理告诉他，餐厅现在有 $n$ 道主菜和 $m$ 道主食，第 $i$ 到主菜的价格为 $a_i$，第 $j$ 道主食的价格为 $b_j$。

餐厅是套餐销售，可以任选一道主菜和一道主食，价格为 $a_i+b_j$。但是餐厅经理发现，很多人会选择价格特别低的组合，餐厅就处于亏损状态，为了避免这种情况出现，餐厅设置了一个最低价格 $P$，如果顾客选择的主菜和主食价格之和低于 $P$，那么就按照 $P$ 进行收费，当然如果高于 $P$，就按照实际价格销售。（即当 $a_i+b_j \leq P$，销售价格为 $P$;当 $a_i+b_j > P$,销售价格为 $a_i+b_j$）

餐厅经理学过乘法原理，知道顾客总共有 $n*m$ 种选择方案，但他想算一算这些方案的价格总和。

输入格式

第一行 3 个整数，$n,m,P$，变量之间空格隔开，含义如题；

第二行 $n$ 个整数，表示 $a_1,a_2, \dots ,a_n$

第三行 $m$ 个整数，表示 $b_1,b_2, \dots,b_m$

输出格式

一个整数，所有方案的价格总和

2 2 7
3 5
6 1

34

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

6978829511

数据规模与约定

$20\%$的数据： $1 \leq n,m\leq 10^3, 1 \leq a_i,b_i \leq 10^3，1\leq P \leq 2 \times 10^3$

$40\%$的数据： $1 \leq n,m\leq 10^4, 1 \leq a_i,b_i \leq 10^4，1\leq P \leq 2 \times 10^4$

$100\%$的数据： $1 \leq n,m\leq 10^5, 1 \leq a_i,b_i \leq 10^5，1\leq P \leq 2 \times 10^5$