说明

自古以来，Dmojistan 和 Pegland 的公民便纷争不断。如今，他们终于签署了停战协议，并决定通过参加双人自行车骑行来庆祝这一和解。两国各有 $N$ 名公民，需将他们两两配对，每组必须包含一名 Dmojistan 公民和一名 Pegland 公民。

每位公民都有各自的骑行速度。每组中，速度较快者操作双人自行车，较慢者只需享受骑行。换言之，若一组两人的速度分别为 $a$ 和 $b$，则该组的自行车速度为 $\max\{a,b\}$（即两者中的较大值）。总速度为 $N$ 个组各自自行车速度的总和。

对于本题，每个测试点会要求你回答以下两个问题之一：

• 问题 $1$：在所有可能的配对方式中，总速度的最小值是多少？

• 问题 $2$：在所有可能的配对方式中，总速度的最大值是多少？

输入格式

输入共有四行。

第一行包含一个整数，表示你要解决的问题类型，该类型为 $1$ 或 $2$。

第二行包含一个正整数 $N(1 \leq N \leq 100)$。

第三行包含 $N$ 个以空格分隔的整数：表示 Dmojistan 公民的骑行速度。

第四行包含 $N$ 个空格分隔的整数：表示 Pegland 公民的骑行速度。

每个人的速度均为整数。若设某位公民的速度为 $v$，保证任意的 $v$ 满足 $1 \le v \le 10^6$。

本题共 $15$ 分。其中 $8$ 分的问题类型为 $1$，$7$ 分的问题类型为 $2$。

输出格式

输出一行表示问题的答案。

1
3
5 1 4
6 2 4

12

2
3
5 1 4
6 2 4

15

2
5
202 177 189 589 102
17 78 1 496 540

2016

提示

样例解释 $1$

存在唯一的最优解：

• 将来自 Dmojistan、速度为 $5$ 的公民，与来自 Pegland、速度为 $6$ 的公民配对。

• 将来自 Dmojistan、速度为 $1$ 的公民，与来自 Pegland、速度为 $2$ 的公民配对。

• 将来自 Dmojistan、速度为 $4$ 的公民，与来自 Pegland、速度为 $4$ 的公民配对。

样例解释 $2$

存在多个可能的最优解。以下是其中一个：

• 将来自 Dmojistan、速度为 $5$ 的公民，与来自 Pegland、速度为 $2$ 的公民配对。

• 将来自 Dmojistan、速度为 $1$ 的公民，与来自 Pegland、速度为 $6$ 的公民配对。

• 将来自 Dmojistan、速度为 $4$ 的公民，与来自 Pegland、速度为 $4$ 的公民配对。

样例解释 $3$

存在多个可能的最优解。以下是其中一个：

• 将来自 Dmojistan、速度为 $202$ 的公民，与来自 Pegland、速度为 $1$ 的公民配对。

• 将来自 Dmojistan、速度为 $177$ 的公民，与来自 Pegland、速度为 $540$ 的公民配对。

• 将来自 Dmojistan、速度为 $189$ 的公民，与来自 Pegland、速度为 $17$ 的公民配对。

• 将来自 Dmojistan、速度为 $589$ 的公民，与来自 Pegland、速度为 $78$ 的公民配对。

• 将来自 Dmojistan、速度为 $102$ 的公民，与来自 Pegland、速度为 $496$ 的公民配对。

总和为 $202+540+189+589+496=2016$。