[R40D]Yet another ICPC problem - 代码源竞赛平台

时空限制

1s/512M

题目描述

apiadu 和 jiangly 要去组队 AK ICPC 了！

ICPC 共有 $n$ 道题，第 $i$ 题对于 apiadu 和 jiangly 的难度分别为 $a_i$ 和 $b_i$。apiadu 和 jiangly 都有一个疲劳值，疲劳值初始为 $0$，一个人每做一道题疲劳值就会加 $1$。当 apiadu 的疲劳值为 $x$ 时他解决第 $i$ 题需要 $a_i+c_x$ 秒，当 jiangly 的疲劳值为 $y$ 时他解决第 $j$ 题需要 $b_j+d_y$ 秒。

每个时刻只能有一个人写题（因为只有一个机位），问他们 AK ICPC 至少需要多少秒？

输入格式

第一行包含一个正整数 $n$，表示题目数量。

接下来一行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n$，具体含义见题目描述。

接下来一行包含 $n$ 个正整数 $b_1,b_2,\dots,b_n$。具体含义见题目描述。

接下来一行包含 $n$ 个正整数 $c_0,c_1,\dots,c_{n-1}$。具体含义见题目描述。

最后一行包含 $n$ 个正整数 $d_0,d_1,\dots,d_{n-1}$。具体含义见题目描述。

样例

样例输入 #1

3
1 3 5
6 4 2
1 2 3
1 2 3

样例输出 #1

10

样例解释 #1

这是样例 $1$ 的一种方案：

• 先由 apiadu 解决问题 $1$，需要 $a_1+c_0=2$ 秒。
• 再由 apiadu 解决问题 $2$，需要 $a_2+c_1=5$ 秒。
• 最后由 jiangly 解决问题 $3$，需要 $b_3+d_0=3$ 秒。

总用时 $10$ 秒，可以证明不存在耗时更少的方案。

样例输入 #2

5
2 4 3 1 2
9 2 5 3 8
1 2 8 3 2
5 4 3 2 1

样例输出 #2

28

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n \le$	$a_i,b_i,c_j,d_j \le$
$1$	$40$	$16$	$100$
$2$	$40$	$3000$	$1000$
$3$	$20$	$2\times 10^5$	$10^9$

对于 $100\%$ 的数据，$1 \le n \le 2\times 10^5$，$1 \le a_i,b_i,c_j,d_j \le 10^9$。