D - Set Menu Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

AtCoder 食堂では N 種類の主菜と M 種類の副菜が提供されており、i 種類目の主菜の価格は A_i、j 種類目の副菜の価格は B_j です。 AtCoder 食堂では新たに定食のメニューを設けることを検討しています。 定食は 1 種類の主菜と 1 種類の副菜から構成され、主菜と副菜の価格の和を 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 bit 符号付き整数型の範囲に収まることが証明できる。

入力例 1

2 2 7
3 5
6 1

出力例 1

24
  • 1 種類目の主菜と 1 種類目の副菜を選んだ場合、定食の価格は \min(3+6,7)=7 です。
  • 1 種類目の主菜と 2 種類目の副菜を選んだ場合、定食の価格は \min(3+1,7)=4 です。
  • 2 種類目の主菜と 1 種類目の副菜を選んだ場合、定食の価格は \min(5+6,7)=7 です。
  • 2 種類目の主菜と 2 種類目の副菜を選んだ場合、定食の価格は \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

Score : 400 points

Problem Statement

AtCoder cafeteria offers N main dishes and M side dishes. The price of the i-th main dish is A_i, and that of the j-th side dish is B_j. The cafeteria is considering introducing a new set meal menu. A set meal consists of one main dish and one side dish. Let s be the sum of the prices of the main dish and the side dish, then the price of the set meal is \min(s,P). Here, P is a constant given in the input.

There are NM ways to choose a main dish and a side dish for a set meal. Find the total price of all these set meals.

Constraints

  • 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
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer as an integer. Under the constraints of this problem, it can be proved that the answer fits into a 64-bit signed integer.

Sample Input 1

2 2 7
3 5
6 1

Sample Output 1

24
  • If you choose the first main dish and the first side dish, the price of the set meal is \min(3+6,7)=7.
  • If you choose the first main dish and the second side dish, the price of the set meal is \min(3+1,7)=4.
  • If you choose the second main dish and the first side dish, the price of the set meal is \min(5+6,7)=7.
  • If you choose the second main dish and the second side dish, the price of the set meal is \min(5+1,7)=6.

Thus, the answer is 7+4+7+6=24.

Sample Input 2

1 3 2
1
1 1 1

Sample Output 2

6

Sample Input 3

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

Sample Output 3

2115597124