题目描述

有 $n$ 张卡牌，每张卡牌的每一面都写着一个二元组 $(p,c)$，表示对应面的标号和收益。保证所有牌的正面标号构成一个排列，反面标号也构成一个排列。

现在你要选出若干张卡牌（可以不选）并翻到合适的面，要求选出的所有面标号互不相同，问对应的收益之和最大是多少。

输入格式

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $p_1,p_2,\cdots,p_n$ 描述正面所有牌的标号。

第三行 $n$ 个正整数 $q_1,q_2,\cdots,q_n$ 描述反面所有牌的标号。

第四行 $n$ 个正整数 $c_1,c_2,\cdots,c_n$ 描述正面所有牌的收益。

第五行 $n$ 个正整数 $d_1,d_2,\cdots,d_n$ 描述反面所有牌的收益。

输出格式

一行，表示最大的收益之和。

样例输入 1

3
1 3 2
2 1 3
10 5 2
-5 2 1

样例输出 1

17

样例解释

最优的方案下，我们应该将第 $1,2,3$ 张卡片都翻到正面，得出的答案会是最大的，为 $p_1+p_2+p_3 = 17$。

样例输入 2

3
1 2 3
1 2 3
10 2 2
-5 5 1

样例输出 2

17

样例解释

最优的方案下，我们应该将第 $1,3$ 张卡片都翻到正面，第 $2$ 张卡片翻到反面，得出的答案会是最大的，为 $p_1+q_2+p_3 = 17$。

样例输入 3

3
1 2 3
1 2 3
10 -2 2
-5 -5 1

样例输出 3

12

样例解释

最优的方案下，我们应该将第 $1,3$ 张卡片都翻到正面，同时不选择第 $2$ 张卡片。这样得出的答案会是最大的，为 $p_1+p_3 = 12$。

测试点约束

本题采用捆绑测试。

数据范围：

• Subtask 1 (10pts)：所有牌的收益都是 $1$。
• Subtask 2 (20pts)：$n\le 15$。
• Subtask 3 (30pts)：$p_i=i$，$q_i=i\bmod n+1$。
• Subtask 4 (40pts)：无特殊限制。

对于全部数据，$1\le n\le 10^6$，$|c_i|,|d_i|\le 10^3$。