P13239 「2.48sOI R1」化妆品

本月 $30$ 日即将迎来埃尔萨纳城的第 $17367$ 次名媛聚会。Misserina 和 ShenTianYi_ 正在为此做准备，她们在商场购买化妆品。

商场里面有 $2n$ 个化妆品，每一个都能提供时尚值和美丽值。任意两个化妆品提供的时尚值互不相同，且美丽值也互不相同。 Misserina 和 ShenTianYi_ 要选择 $n$ 次心仪的化妆品，每一次 Misserina 先选，ShenTianYi_ 后选。Misserina 是个性格多变的人，她时而希望自己更加时尚，时而希望自己更加美丽，会选择剩余的化妆品中该值最大的那一个；而 ShenTianYi_ 则是淑女中的淑女，每一次 Misserina 选择她想要的之后她都会选择 Misserina 最不想要的那个，也就是对应时尚值或美丽值最小的那个。 她们想知道，按照这个规则选完所有化妆品之后，两人的时尚值和美丽值分别为多少。请帮她们解答这个问题。

第一行：一个整数 $n$，含义如题干所示。 第二行：$2n$ 个整数 $F_1,F_2,\dots,F_{2n}$，表示每一个化妆品提供的时尚值。 第三行：$2n$ 个整数 $B_1,B_2,\dots,B_{2n}$，表示每一个化妆品提供的美丽值。 第四行：$n$ 个整数 $Q_1,Q_2,\dots,Q_n$，表示 Misserina 每次希望购买时尚值最高的（用 `1` 表示）还是美丽值最高的（用 `2` 表示）。

第一行两个整数，分别表示最终 Misserina 的时尚值和美丽值。 第二行两个整数，分别表示最终 ShenTianYi_ 的时尚值和美丽值。

第一次选择： Misserina 选择时尚值最高的即第 $5$ 种化妆品，ShenTianYi_ 选择时尚值最低的即第 $1$ 种化妆品。 第二次选择： Misserina 选择剩下的时尚值最高的即第 $4$ 种化妆品，ShenTianYi_ 选择剩下的时尚值最低的第 $3$ 种化妆品。 第三次选择： Misserina 选择剩下的美丽值最高的第 $6$ 种化妆品，ShenTianYi_ 选择剩下的美丽值最低的第 $2$ 种化妆品。 最终 Misserina 的时尚值为 $8+9+4=21$，美丽值为 $3+4+27=34$；ShenTianYi_ 的时尚值为 $1+7+3=11$，美丽值为 $1665+5+8888=10558$。 对于 $100\%$ 数据： - $1 \le n \le 5 \times 10^5$； - $1 \le F_i,B_i \le 10^9$； - $Q_i \in \{1,2\}$； - $\forall\: i \ne j$，$F_i \ne F_j$，$B_i \ne B_j$。 **本题采取捆绑测试。** - Subtask 0（9 pts）：$1 \le n \le 1000$，$1 \le F_i,B_i \le 2000$，$Q_i$ 均为 `1` 或均为 `2`； - Subtask 1（11 pts）：$1 \le n \le 1000$，$1 \le F_i,B_i \le 2000$； - Subtask 2（20 pts）：$1 \le n \le 1000$，$1 \le F_i,B_i \le 10^9$； - Subtask 3（26 pts）：$1 \le n \le 5 \times 10^5$，$1 \le F_i,B_i \le 10^9$，$Q_i$ 均为 `1` 或均为 `2`； - Subtask 4（34 pts）：$1 \le n \le 5 \times 10^5$，$1 \le F_i,B_i \le 10^9$。