103213: [Atcoder]ABC321 D - Set Menu

Memory Limit：256 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：9 Solved：0

Description

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

Output

得分：400分 部分 问题说明 AtCoder食堂提供$N$种主菜和$M$种配菜。第$i$种主菜的价格是$A_i$，第$j$种配菜的价格是$B_j$。食堂正在考虑推出一种新的套餐菜单。套餐由一份主菜和一份配菜组成。设主菜和配菜价格之和为$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位带符号整数。 部分 样例输入1 ``` 2 2 7 3 5 6 1 ``` 部分 样例输出1 ``` 24 ``` * 如果你选择第一个主菜和第一个配菜，套餐的价格为$\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$。 部分 样例输入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 ```

HINT

n个主食和m个小菜，一顿饭两种各来一个，费用为他们之和，如果费用超过p，则只需要花费p，请问这m*n种搭配的套餐费用之和是多少？

Source/Category

加入题单

算法标签：