#2366. 「BalticOI 2008」手套

内存限制:64 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: HeRaNO

题目描述

题目译自 BalticOI 2008 Day2「Gloves

化学教授名曰「酸雨」。在他家黑暗的地下室,有两个装有手套的抽屉,一个抽屉装左手手套,另一个装右手手套。每个抽屉中有 n 种不同颜色的手套。教授知道在每个抽屉中,每种颜色的手套数目(在不同抽屉中,相同颜色的手套数目可能不同)。保证他能够找到同色的一副手套。
只有教授带相同颜色的一副手套时试验才可能会成功(与哪种颜色无关),所以在每次试验开始之前他都要去地下室从抽屉中拿手套,并且希望至少有一副一样颜色的手套。但是地下室太黑了,不出地下室就不可能分辨出任何手套的颜色。教授讨厌去地下室超过一次,同时也讨厌拿一堆手套回实验室(以防没有相同颜色的手套)。

任务

写一个程序能够:

  • 从标准输入中读取颜色种数和每种颜色手套的数目
  • 计算在确保拿出的手套中有一副颜色相同的手套的情况下需要取出手套的最小数目(需要明确指出从每个抽屉中取出手套的确切数目)
  • 将结果写到标准输出

输入格式

标准输入的第一行包含一个正整数 n 1\le n\le 20 )描述不同的颜色种数。颜色从 1 n 编号;
输入第二行包含 n 个非负整数 0\le a_1,a_2,\cdots ,a_n\le 10^8 a_i 表示在装左手手套的抽屉中第 i 种颜色手套的数目;
输入第三行包含 n 个非负整数 0\le b_1,b_2,\cdots ,b_n\le 10^8 b_i 表示在装右手手套的抽屉中第 i 种颜色手套的数目。

输出格式

标准输出第一行包含单独一个整数,表示从装左手手套抽屉中取出的手套数。第二行包含单独一个整数,表示从装右手手套抽屉中取出的手套数。这两个数的总和应尽量小。
如果有多种正确答案,你的程序可以输出任意一组。

样例

样例输入

4
0 7 1 6
1 5 0 6

样例输出

2
8

数据范围与提示

40 n\le 4 a_i,b_i\le 10
对于所有数据, 1\le n\le 20